سفر پویان


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

پویان می‌خواهد از شهر «تهران» به شهر «شیراز» برود. در کشور پویان یک شهر «اصفهان» وجود دارد.

  • می‌دانیم xx جاده‌ی مختلف و دو طرفه بین «تهران» و «شیراز» داریم.
  • می‌دانیم yy جاده‌ی مختلف و دو طرفه بین «تهران» و «اصفهان» داریم.
  • می‌دانیم zz جاده‌ی مختلف و دو طرفه بین «شیراز» و «اصفهان» داریم.

پویان می‌خواهد با طی کردن حداکثر ۳ جاده از «تهران» به «شیراز» برسد به طوری که هیچ جاده‌ای را بیش از یک بار طی نکند. (چه رفت چه برگشت)

از شما می‌خواهیم تعداد روش‌های ممکن برای انجام این سفر را محاسبه کنید. دو روش برای سفر با هم فرق دارد اگر دنباله‌ی جاده‌هایی که در این سفر طی می‌شود متفاوت باشد.

ورودی🔗

در هر ورودی به شما tt سناریو داده می‌شود. 1t2001 \leq t \leq 200

در تنها سطر هر سناریو، سه عدد صحیح xx، yy و zz که با یک فاصله از هم جداشده‌اند داده می‌شود.

0x,y,z1000 \leq x, y, z \leq 100

خروجی🔗

خروجی tt سطر دارد که جواب هر سطر، یک عدد صحیح، نشان دهنده‌ی پاسخ سناریو است.

مثال🔗

ورودی نمونه ۱🔗

3
1 1 1
3 0 0
2 1 3
Plain text

خروجی نمونه ۱🔗

2
9
17
Plain text

سناریو اول. پویان می‌تواند مستقیم از تهران به شیراز برود. یا از تهران به اصفهان برود و سپس از اصفهان به شیراز برود. برای هر کدام از این دو حالت یک روش برای انتخاب جاده‌ها دارد.

سناریو دوم. پویان می‌تواند مستقیم از تهران به شیراز برود و به سفر خود پایان بدهد. برای انجام این کار ۳ جاده مختلف می‌تواند انتخاب کند. همچنین می‌تواند ابتدا از تهران به شیراز برود و سپس از شیراز به تهران برگردد (نه از جاده‌ای که رفته) و در نهایت از تنها جاده‌ی باقی‌مانده به شیراز برود. برای این کار ۶ روش وجود دارد. بنابراین پاسخ مسئله ۶ + ۳ = ۹ است.