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.