ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Junior Contest, October 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Yekaterinburg Subway 2

Time limit: 1.0 second
Memory limit: 64 MB
As you all know, Yekaterinburg Subway has only one line. All stations of our subway are genuine architectural masterpieces. Yekaterinburg's citizens are not very happy, though, as they have to travel from home to work and then back home every day. Traffic jams are ubiquitous in Yekaterinburg, hence every citizen dreams of new subway stations near his house and work.
Yekaterinburg's municipal government decided to take into account the wishes of the citizens. The Strategic Plan Of Subway Development (up to the year 2523) was approved at a conference organized by Yekaterinburg's Mayor. By the eight-hundredth anniversary of Yekaterinburg the Subway will consist of 70 stations!
Somehow you managed to get a map of Yekaterinburg Subway as of 2523 (see the picture). The map contains 8 lines formed by 70 stations; many stations are transit ones. From 2 to 4 different underground lines can intersect at transit stations. You are to find the amount of time required to get from one given station to another. Trains of the future will travel between any two adjacent stations in 1 minute. Moreover, line-to-line transfer at any transit station is considered to take no time (after all, you don't have to examine stations carefully as opposed to tourists who will arrive in Yekaterinburg only to admire the Subway). The time of waiting for a train at a station shouldn't be taken into account.
Problem illustration

Input

The first line of the input contains an integer N, which is the number of tests (1 ≤ N ≤ 4900). The next N lines contain tests. Each test consists of two station names separated by exactly one space. The names contain only uppercase and lowercase latin letters and underscores. Every station name, except for “Prospekt_Kosmonavtov” and “Kamennye_palatki”, is given exactly as on the map.

Output

For each test you are to output the minimal number of minutes required to travel from the first station to the second station. The answer for each test should be written in a separate line.

Sample

inputoutput
6
Prospekt_Kosmonavtov Geologicheskaya
Shevchenko Vilonovskaya
Koltsovo Zelyony_ostrov
Teatralnaya Kamennye_palatki
China_town Italyanskaya
1905_year_square 1905_year_square
6
3
11
3
9
0
Problem Author: Alexander Ipatov
Problem Source: USU Junior Contest, October 2007
To submit the solution for this problem go to the Problem set: 1575. Yekaterinburg Subway 2