B. Longest Divisors Interval

time limit per test

2 seconds

memory limit per test

256 megabytes

Given a positive integer nn, find the maximum size of an interval [l,r][l,r] of positive integers such that, for every ii in the interval (i.e., l≤i≤rl≤i≤r), nn is a multiple of ii.

Given two integers l≤rl≤r, the size of the interval [l,r][l,r] is r−l+1r−l+1 (i.e., it coincides with the number of integers belonging to the interval).

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.

The only line of the description of each test case contains one integer nn (1≤n≤10181≤n≤1018).

Output

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

Example

Input

Copy

10

1

40

990990

4204474560

169958913706572972

365988220345828080

387701719537826430

620196883578129853

864802341280805662

1000000000000000000

Output

Copy

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][1,1] (it's valid because n=1n=1 is a multiple of 11) and its size is 11.

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

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

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

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

解题说明：此题是一道数学题，给出一整数n，要求在1到n内找出一连续区间，使区间内每个数都是n的因数，求满足要求的最长区间。可以从1~n遍历，统计有多少个i能被n整除，遇到不能被整除的就输出答案即可。

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int main()
{int t;cin >> t;while (t--){long long n;cin >> n;int cnt = 0;int ans = 0;for (int i = 1; i <= n; i++){if (n % i == 0){cnt++;}else{break;}}cout << cnt << endl;}return 0;
}