Time Limit: 2.5 s

Memory Limit: 256.0 MB

Description

You are given a positive integer N. Your task is to select a positive integer L (1 ≤ L ≤ N),then compute the sum S(L) of numbers from 1 to L:

S(L) = 1 + 2 + 3 + ... + L.

Once you compute the sum S(L), the next step is to find the number of divisors of S(L). A divisor of S(L) is any positive integer that divides S(L) evenly (without leaving a remainder). For example, the divisors of 6 are 1, 2, 3, and 6.

Your goal is to select L such way that S(L) has maximum number of divisors.

Input

• The first line of input contains an integer T (\(1\) ≤ T ≤ \(10^5\))— the number of test cases.
• Then T lines follow, each containing a single integer N (\(1\) ≤ N ≤ \(10^6\)).

Output

• For each test case, print a single integer: the maximum number of divisors of S(L) found by selecting L optimally.

Sample

5
1
5
3
10
2

1
4
4
9
2

Sample test case:

• For the second test case, N = 5, the optimal L is L = 4 (1 ≤ L ≤ N), where S(4) = 10, and the number of divisors of 10 is 4. {1, 2, 5, 10}
• For the fourth test case, N = 10, the optimal L is L = 8 (1 ≤ L ≤ N), where S(8) = 36, and the number of divisors of 36 is 9.