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

نقشه متروی تهران را در نظر بگیرید. (این عکس فقط برای دادن یک دید کلی به شماست و نیازی به خواندن کلمات آن نیست.)

اسم تمام ایستگاه‌ها در این فایل در ۷ سطر آمده است. در سطر $i$ام، نام ایستگاه‌های خط $i$ام مترو به ترتیب و با فاصله آمده است. (توجه کنید نام یک ایستگاه شامل کاراکتر فاصله (space) نیست.)

• زمان لازم تردد قطار بین دو ایستگاه ۲ دقیقه
• زمان لازم برای ورود به ایستگاهی که قصد سوار شدن قطار را داریم، ۱۷ دقیقه
• زمان لازم برای خارج شدن از ایستگاه که قصد پیاده زدن در آن را داریم، ۱۲ دقیقه.
• زمان لازم برای تعویض خط نیاز داریم، نیز ۱۰ دقیقه است.

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

محسن می‌خواهد خریدهای خودش را از دیجیکالا انجام ندهد و با مترو برود و خرید کند. او بعد از مسیریابی فهمید که باید از ایستگاه $s$ سوار مترو شود و در ایستگاه $f$ پیاده شود.

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

ورودی

در سطر اول ورودی عدد صحیح و مثبت $q$ آمده است. $$1 \leq q \leq 16000$$ در $q$ سطر بعدی در هر سطر دو رشته $s$ و $f$ آمده که نام ایستگاه شروع و پایان را نشان می‌دهد.

تضمین می‌شود این دو رشته در فایل ایستگاه‌ها موجوداند.

خروجی

برای هر کدام از $q$ جفت ایستگاه ورودی داده شده، کمینه زمان لازم برای رسیدن از ایستگاه مبدا به ایستگاه مقصد را محاسبه کنید.

مثال

ورودی نمونه ۱

5
Tajrish Gheytariyeh
Tajrish Gholhak
Tarasht Eram-e_Sabz
Aghdasiyeh Sohrevardi
Towhid Baharestan

خروجی نمونه ۱

31
35
43
45
51

سفر اول از «تجریش» به «قیطریه»:

• ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «تجریش» طول می‌کشد.
• ۲ دقیقه طول می‌کشد تا در خط ۱، از ایستگاه «تجریش» به «قیطریه» برسد.
• ۱۲ دقیقه طول می‌کشد تا از ایستگاه «قیطریه» خارج شود.

بنابراین مجموع زمان این سفر برابر است با: $$17 + 2 + 12 = 31$$

سفر دوم از «تجریش» به «قلهک»:

• ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «تجریش» طول می‌کشد.
• ۶ دقیقه طول می‌کشد تا در خط ۱، از ایستگاه «تجریش» به «قلهک» برسد.
• ۱۲ دقیقه طول می‌کشد تا از ایستگاه «قلهک» خارج شود.

بنابراین مجموع زمان این سفر برابر است با: $$17 + 6 + 12 = 35$$

سفر سوم از «طرشت» به «ارم سبز»:

• ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «طرشت» طول می‌کشد.
• ۲ دقیقه طول می‌کشد تا در خط ۲، از ایستگاه «طرشت» به «تهران (صادقیه)» برسد.
• ۱۰ دقیقه طول می‌کشد تا از خط از ۲ به ۵ در ایستگاه «تهران (صادقه)» تغییر مسیر بدهد.
• ۲ دقیقه طول می‌کشد تا در خط ۵، از ایستگاه «تهران (صادقیه)» به «ارم سبز» برسد.
• ۱۲ دقیقه طول می‌کشد تا از ایستگاه «ارم سبز» خارج شود.

بنابراین مجموع زمان این سفر برابر است با: $$17 + 2 + 10 + 2 + 12 = 43$$

سفر چهارم از «اقدیسه» به «سهروردی»:

• ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «اقدسیه» طول می‌کشد.
• ۱۶ دقیقه طول می‌کشد تا در خط ۳، از ایستگاه «اقدسیه» به «سهروردی» برسد.
• ۱۲ دقیقه طول می‌کشد تا از ایستگاه «سهروردی» خارج شود.

بنابراین مجموع زمان این سفر برابر است با: $$17 + 16 + 12 = 45$$

سفر پنجم از «توحید» به «بهارستان»:

• ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «توحید» طول می‌کشد.
• ۱۰ دقیقه طول می‌کشد تا در خط ۴، از ایستگاه «توحید» به «دروازه شمیران» برسد.
• ۱۰ دقیقه طول می‌کشد تا از خط از ۴ به ۲ در ایستگاه «دروازه شمیران» تغییر مسیر بدهد.
• ۲ دقیقه طول می‌کشد تا در خط ۵، از ایستگاه «دروازه شمیران» به «بهارستان» برسد.
• ۱۲ دقیقه طول می‌کشد تا از ایستگاه «بهارستان» خارج شود.

بنابراین مجموع زمان این سفر برابر است با: $$17 + 10 + 10 + 2 + 12 = 51$$