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.
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.
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.
Problem Author: Alexander Ipatov
Problem Source: USU Junior Contest, October 2007