Архів складається з папок, пронумерованих від до . Деякі пари папок безпосередньо пов'язані посиланнями, всього таких посилань n - 1, і з будь-якої папки можна перейти за посиланнями до будь-якої іншої; інакше кажучи, папки та посилання утворюють дерево. Папка є кореневою.
Для кожної папки v \ne s її батьківською папкою називається сусід на шляху від до кореневої папки, а називається підпапкою своєї батьківської папки.
Кожній папці треба дати назву f_v — додатне ціле число. За правилами архіву назви мають задовольняти такі умови:
коренева папка має назву f_s = 1;
назва кожної іншої папки кратна назві її батьківської папки , тобто f_v = k \cdot f_p для деякого додатного цілого (випадок k = 1 дозволений: підпапка може мати ту саму назву, що й батьківська папка);
дві підпапки однієї папки мусять мати різні назви.
Короткі назви легше набирати, тому адміністратор хоче, щоб найбільша назва в архіві була якомога меншою. Знайдіть мінімально можливе значення \max\limits_{1 \le v \le n} f_v.
Перший рядок містить одне ціле число (1 \le t \le 5 \cdot 10^5) — кількість тестових випадків.
Перший рядок кожного тестового випадку містить два цілі числа та (1 \le s \le n \le 5 \cdot 10^5) — кількість папок і номер кореневої папки. Кожен із наступних n - 1 рядків містить два цілі числа та (1 \le u, v \le n, u \ne v) — папки, пов'язані посиланням. Гарантується, що посилання утворюють дерево.
Сума за всіма тестовими випадками не перевищує 5 \cdot 10^5.
Для кожного тестового випадку виведіть одне ціле число — мінімально можливу найбільшу назву.
Приклад 1
У першому тестовому випадку коренева папка — , і вона має підпапки , і . Папка має підпапки і , а папка — підпапки і . Одне з оптимальних призначень назв:
f_4 = 1;
f_1 = 1, f_2 = 2, f_8 = 3;
f_3 = 1, f_5 = 2;
f_6 = 2, f_7 = 4.
Можна показати, що найбільша назва не може бути меншою за .
У другому тестовому випадку папки утворюють ланцюжок 1 - 2 - 3 - 4 - 5 з кореневою папкою посередині. Папки і є підпапками кореневої папки, тому їм потрібні різні назви. Наприклад, f_1 = f_2 = f_3 = 1 і f_4 = f_5 = 2, тож відповідь — .
У третьому тестовому випадку є лише коренева папка, і f_1 = 1.