Arxiv -dən -ə qədər nömrələnmiş qovluqdan ibarətdir. Bəzi qovluq cütləri bilavasitə keçidlərlə bağlıdır, belə keçidlərin ümumi sayı n - 1-dir və istənilən qovluqdan keçidlər vasitəsilə istənilən digər qovluğa keçmək olar; başqa sözlə, qovluqlar və keçidlər ağac əmələ gətirir. qovluğu kök qovluqdur.
Hər bir v \ne s qovluğu üçün onun valideyn qovluğu -dən kök qovluğa gedən yolda -nin qonşusudur, isə öz valideyninin alt qovluğu adlanır.
Hər bir qovluğuna müsbət tam ədəd olan f_v adı verilməlidir. Arxivin qaydalarına görə adlar aşağıdakı şərtləri ödəməlidir:
kök qovluğun adı f_s = 1;
hər bir digər qovluğunun adı onun valideyn qovluğunun adının qatıdır, yəni hansısa müsbət tam üçün f_v = k \cdot f_p (k = 1 halına icazə verilir: alt qovluq valideyni ilə eyni ada malik ola bilər);
eyni qovluğun iki alt qovluğunun adları fərqli olmalıdır.
Qısa adları yazmaq daha asandır, ona görə də administrator arxivdəki ən böyük adın mümkün qədər kiçik olmasını istəyir. \max\limits_{1 \le v \le n} f_v ifadəsinin mümkün minimal qiymətini tapın.
Birinci sətirdə bir tam ədəd (1 \le t \le 5 \cdot 10^5) — test hallarının sayı verilir.
Hər test halının birinci sətrində iki tam ədəd və (1 \le s \le n \le 5 \cdot 10^5) — qovluqların sayı və kök qovluğun nömrəsi verilir. Sonrakı n - 1 sətrin hər birində iki tam ədəd və (1 \le u, v \le n, u \ne v) — keçidlə bağlanmış qovluqlar verilir. Zəmanət verilir ki, keçidlər ağac əmələ gətirir.
Bütün test halları üzrə qiymətlərinin cəmi 5 \cdot 10^5-i aşmır.
Hər test halı üçün bir tam ədəd — mümkün olan minimal ən böyük adı çap edin.
Nümunə 1
Birinci test halında kök qovluq -dür və onun , və alt qovluqları var. qovluğunun və alt qovluqları, qovluğunun isə və alt qovluqları var. Adların optimal təyinatlarından biri belədir:
f_4 = 1;
f_1 = 1, f_2 = 2, f_8 = 3;
f_3 = 1, f_5 = 2;
f_6 = 2, f_7 = 4.
Göstərmək olar ki, ən böyük ad -dən kiçik ola bilməz.
İkinci test halında qovluqlar ortasında kök qovluğu olan 1 - 2 - 3 - 4 - 5 zənciri əmələ gətirir. və qovluqları kök qovluğun alt qovluqlarıdır, ona görə də onların adları fərqli olmalıdır. Məsələn, f_1 = f_2 = f_3 = 1 və f_4 = f_5 = 2, deməli cavab -dir.
Üçüncü test halında yalnız kök qovluq var və f_1 = 1.