Миша и Гриша — веселые ребята, поэтому они любят кататься на новом метро. В метро есть n станций, соединенных n - 1 перегонами так, что каждый перегон соединяет две станции, и от каждой станции до любой другой можно добраться по перегонам.
Ребята решили повеселиться и затеяли кое-что. А именно, в какой-нибудь день утром Миша проезжает кратчайшим путем от станции s до станции f, и на каждой из станций, мимо которых он проехал (включая s и f), он рисует баллончиком корявую надпись «Здесь был Миша». После чего вечером того же дня, Гриша едет со станции t до станции f кратчайшим путем и считает количество станций, на которых обнаружит надпись Миши. После этого ночью этого же дня работники метро смывают все эти надписи, потому что метро должно быть чистым.
Ребята уже выбрали на несколько дней вперед по три станции a, b и c, одна из которых должна стать станцией s, другая — станцией f, а третья — станцией t в каждый из дней. Им стало интересно, как нужно выбрать из этих трех станций s, f, t так, чтобы число, которое насчитает Гриша, было максимально возможным. Они просят вас помочь им.
Выходные данные
Выведите q строк. В i-й строке выведите максимальное число, которое может насчитать Гриша при оптимальном выборе s, t и f из трех станций в i-й день.
Примечание
В первом примере в первый день при s = 1, f = 2, t = 3, Миша поедет по маршруту 1 
2, а Гриша по маршруту 3 1 2. Он увидит надпись на станциях 1 и 2. Во второй день при s = 3, f = 2, t = 3, оба мальчика едут по маршруту 3 1 2. Гриша видит надпись на 3 станциях.
Во втором примере при s = 1, f = 3, t = 2, Миша поедет по маршруту 1 2 3, а Гриша по маршруту 2 3 и увидит надпись на обеих станциях.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 1
1 2 3
2 3 3
|
2
3
|
|
2
|
4 1
1 2 3
1 2 3
|
2
|