Un archivo consta de carpetas numeradas de a . Algunos pares de carpetas están enlazados directamente, hay n - 1 enlaces en total, y desde cualquier carpeta se puede llegar a cualquier otra siguiendo los enlaces; en otras palabras, las carpetas y los enlaces forman un árbol. La carpeta es la carpeta raíz.
Para cada carpeta v \ne s, su carpeta padre es el vecino de en el camino de a la carpeta raíz, y se denomina subcarpeta de su padre.
A cada carpeta se le debe asignar un nombre f_v, que es un entero positivo. Según las reglas del archivo, los nombres deben cumplir las siguientes condiciones:
la carpeta raíz tiene el nombre f_s = 1;
el nombre de cualquier otra carpeta es un múltiplo del nombre de su carpeta padre , es decir, f_v = k \cdot f_p para algún entero positivo (se permite el caso k = 1: una subcarpeta puede tener el mismo nombre que su padre);
dos subcarpetas de una misma carpeta deben tener nombres distintos.
Los nombres cortos son más fáciles de escribir, por eso el administrador quiere que el mayor nombre del archivo sea lo más pequeño posible. Encuentre el mínimo valor posible de \max\limits_{1 \le v \le n} f_v.
La primera línea contiene un único entero (1 \le t \le 5 \cdot 10^5) — el número de casos de prueba.
La primera línea de cada caso de prueba contiene dos enteros y (1 \le s \le n \le 5 \cdot 10^5) — el número de carpetas y el número de la carpeta raíz. Cada una de las siguientes n - 1 líneas contiene dos enteros y (1 \le u, v \le n, u \ne v) — las carpetas conectadas por un enlace. Se garantiza que los enlaces forman un árbol.
La suma de sobre todos los casos de prueba no supera 5 \cdot 10^5.
Para cada caso de prueba imprima un entero — el mínimo valor posible del mayor nombre.
Ejemplo 1
En el primer caso de prueba la carpeta raíz es , y tiene las subcarpetas , y . La carpeta tiene las subcarpetas y , y la carpeta tiene las subcarpetas y . Una asignación óptima de nombres es:
f_4 = 1;
f_1 = 1, f_2 = 2, f_8 = 3;
f_3 = 1, f_5 = 2;
f_6 = 2, f_7 = 4.
Se puede demostrar que el mayor nombre no puede ser menor que .
En el segundo caso de prueba las carpetas forman la cadena 1 - 2 - 3 - 4 - 5 con la carpeta raíz en el medio. Las carpetas y son subcarpetas de la carpeta raíz, por lo que necesitan nombres distintos. Por ejemplo, f_1 = f_2 = f_3 = 1 y f_4 = f_5 = 2, así que la respuesta es .
En el tercer caso de prueba solo hay la carpeta raíz, y f_1 = 1.