Problem Statement is easy, for a given number N, you have to print the base B such that if we write N in base B then it would contain most 0's at the end.

If more then one such base exist, which satisfy the given condition then print the smallest such base.

Input

The first line of the input consist of a single integer number t which determines the number of tests.

In each of next t lines there is a single integer number N.

Constraints

• 0 < t ≤ 10⁵
• 2 ≤ N ≤ 10¹²

Output

Output contains one line with one integer B such that N written in base B has the most zeros at the end and is the smallest B with this property.

Example

Input:
2
72
18

Output:
2
3

Explanation

The answer for N=72 is B=2, because 72=1001000₂ (72 written in base 2) has 3 zeros at the end.

Using base 3, we only get 2 zeroes at the end (because 72=2200₃),

using base 6 would also give us 2 zeros, and no other base would give us more than 1 zero

For 18, 18=10010₂ and 18=200₃ so answer will be 3.

Note: Test case were regenerated on 23 June 2020.

As rejudge is disabled by SPOJ please submit your code again.