Longest Divisors Interval

Description:

Input:

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of the description of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$).

Output:

For each test case, print a single integer: the maximum size of a valid interval.

Sample Input:

10
1
40
990990
4204474560
169958913706572972
365988220345828080
387701719537826430
620196883578129853
864802341280805662
1000000000000000000

Sample Output:

1
2
3
6
4
22
3
1
2
2

Note:

In the first test case, a valid interval with maximum size is $$$[1, 1]$$$ (it's valid because $$$n = 1$$$ is a multiple of $$$1$$$) and its size is $$$1$$$.

In the second test case, a valid interval with maximum size is $$$[4, 5]$$$ (it's valid because $$$n = 40$$$ is a multiple of $$$4$$$ and $$$5$$$) and its size is $$$2$$$.

In the third test case, a valid interval with maximum size is $$$[9, 11]$$$.

In the fourth test case, a valid interval with maximum size is $$$[8, 13]$$$.

In the seventh test case, a valid interval with maximum size is $$$[327869, 327871]$$$.