Как вы знаете, в Екатеринбурге всего одна линия метро. Каждая станция нашего метрополитена — настоящий архитектурный шедевр. Впрочем, это не очень-то радует жителей Екатеринбурга, которым приходится каждый день утром ехать из дома на работу или на учёбу, а вечером — назад. В любом районе Екатеринбурга в любое время суток огромные пробки, поэтому, конечно, все жители мечтают о том, чтобы рядом с их домом и работой как можно скорее были бы построены новые станции метро.

Мэрия Екатеринбурга решила учесть пожелания горожан. На совещании у Главы города был принят Стратегический план развития метро в Екатеринбурге на срок до 2523 года. Планируется, что к 800-летию Екатеринбурга метрополитен будет состоять из 70 станций!

Вам, неизвестно каким образом, попалась в руки схема Екатеринбургского метро 2523 года (см. рисунок). На схеме 70 станций, формирующих 8 линий; многие станции являются пересадочными. На пересадочных станциях может пересекаться от 2 до 4 различных линий метро. Вам стало интересно, сколько времени потребуется, чтобы добраться от одной станции до другой. Известно, что метропоезда будущего смогут преодолевать любой перегон Екатеринбургского метро ровно за 1 минуту. Кроме того, пересадку с любой линии на любую на пересадочной станции можно считать мгновенной (Вам ведь не нужно внимательно осматривать станции, в отличие от туристов, которые будут приезжать в Екатеринбург только для того, чтобы полюбоваться красотами нашего метро). Временем ожидания поезда также следует пренебречь.

В первой строке находится целое число N — количество тестов (1 ≤ N ≤ 4900). Далее в N строках перечислены тесты. Каждый тест состоит из названий 2-х станций, разделённых ровно одним пробелом. Названия могут содержать маленькие и большие латинские буквы, а также символы подчёркивания. Названия всех станций, кроме «Prospekt_Kosmonavtov» и «Kamennye_palatki», приведены на схеме метро точно так же, как они будут представлены на вводе.

Для каждого теста выведите, сколько минут минимум потребуется для того, чтобы добраться от первой станции до второй. Каждый ответ должен располагаться в отдельной строке.