An archive consists of folders numbered from to . Some pairs of folders are directly linked, there are n - 1 such links in total, and from any folder one can reach any other one through the links; in other words, the folders and the links form a tree. Folder is the root folder.
For every folder v \ne s, its parent folder is the neighbour of on the path from to the root folder, and is called a subfolder of its parent.
Every folder must be given a name f_v, which is a positive integer. By the convention of the archive, the names must satisfy the following rules:
the root folder is named f_s = 1;
the name of every other folder is a multiple of the name of its parent folder , that is, f_v = k \cdot f_p for some positive integer (the case k = 1 is allowed: a subfolder may have the same name as its parent);
two subfolders of the same folder must have different names.
Short names are easier to type, so the administrator wants the largest name in the archive to be as small as possible. Find the minimum possible value of \max\limits_{1 \le v \le n} f_v.
The first line contains a single integer (1 \le t \le 5 \cdot 10^5) — the number of test cases.
The first line of each test case contains two integers and (1 \le s \le n \le 5 \cdot 10^5) — the number of folders and the number of the root folder. Each of the next n - 1 lines contains two integers and (1 \le u, v \le n, u \ne v) — the folders connected by a link. It is guaranteed that the links form a tree.
The sum of over all test cases does not exceed 5 \cdot 10^5.
For each test case print one integer — the minimum possible largest name.
Example 1
In the first test case the root folder is , and it has the subfolders , and . Folder has the subfolders and , and folder has the subfolders and . One optimal assignment of names is:
f_4 = 1;
f_1 = 1, f_2 = 2, f_8 = 3;
f_3 = 1, f_5 = 2;
f_6 = 2, f_7 = 4.
It can be shown that the largest name cannot be less than .
In the second test case the folders form the chain 1 - 2 - 3 - 4 - 5 with the root folder in the middle. Folders and are subfolders of the root folder, so they need different names. For example, f_1 = f_2 = f_3 = 1 and f_4 = f_5 = 2, so the answer is .
In the third test case there is only the root folder, and f_1 = 1.