D. The FFT Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Eddard has wanted to learn about FFT for a very long time, but he's a little lazy and is intimidated by its difficulty and complexity. However, he found a simple meme explaining what the Fourier Transform is.

Fourier Transform explanation. (Check the notes if the image is not loading.

He decided to find a fast algorithm that can find the base for any number that makes it the "Fouriest", basically inventing the Fast Fourier Transform. Can you help him?

Input

The first line of input consists of a single integer $$$T (1 \le T \le 10)$$$, the number of test cases.

Each test case is given in one line containing a single integer $$$n(5 \le n \le 10^{12})$$$

Output

For each test case, print a single integer $$$b(2 \le b \le 2 \cdot 10^{12})$$$, the base where $$$n$$$ becomes "Fouriest". If no $$$b$$$ exists where the representation of $$$n$$$ has at least 1 four, print $$$-1$$$. If multiple solutions exist, print the largest.

Example
Input
4
10
24
20
44444
Output
6
5
16
10
Note

Test Cases Explanation:

$$$(10)_{10}$$$ = $$$(14)_6$$$

$$$(24)_{10}$$$ = $$$(44)_5$$$

$$$(20)_{10}$$$ = $$$(40)_{5}$$$ = $$$(14)_{16}$$$ Here, $$$20$$$ produces $$$1$$$ four in both bases $$$5$$$ and $$$16$$$, but $$$16$$$ is greater.

$$$44444$$$ is fouriest in base $$$10$$$

Image description:

It's called a Fourier Transform when you take a number and convert it to the base system where it will have more fours, thus making it "Fourier". If you pick the base with the most fours, the number is said to be "Fouriest".