310582: CF1855B. Longest Divisors Interval

B. Longest Divisors Intervaltime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Given a positive integer $n$, find the maximum size of an interval $[l, r]$ of positive integers such that, for every $i$ in the interval (i.e., $l \leq i \leq r$), $n$ is a multiple of $i$.

Given two integers $l\le r$, the size of the interval $[l, r]$ is $r-l+1$ (i.e., it coincides with the number of integers belonging to the interval).

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.

ExampleInput

10
1
40
990990
4204474560
169958913706572972
365988220345828080
387701719537826430
620196883578129853
864802341280805662
1000000000000000000

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]$.

题目大意：
给定一个正整数 $ n $，找出一个最大的区间 $[l, r]$ 使得区间内的每一个整数 $ i $ （即 $ l \leq i \leq r $）都是 $ n $ 的因数。区间的长度定义为 $ r - l + 1 $。

输入数据格式：
第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）—— 测试用例的数量。
每个测试用例包含一行，有一个整数 $ n $（$ 1 \leq n \leq 10^{18} $）。

输出数据格式：
对于每个测试用例，输出一个整数：有效区间的最大长度。

请注意，题目中的公式是使用 LaTeX 格式编写的，确保在适合的平台上渲染以显示为数学公式。题目大意： 给定一个正整数 $ n $，找出一个最大的区间 $[l, r]$ 使得区间内的每一个整数 $ i $ （即 $ l \leq i \leq r $）都是 $ n $ 的因数。区间的长度定义为 $ r - l + 1 $。 输入数据格式： 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）—— 测试用例的数量。 每个测试用例包含一行，有一个整数 $ n $（$ 1 \leq n \leq 10^{18} $）。 输出数据格式： 对于每个测试用例，输出一个整数：有效区间的最大长度。 请注意，题目中的公式是使用 LaTeX 格式编写的，确保在适合的平台上渲染以显示为数学公式。