Valuable Factorial

Let us define the essential value of a factorial n! = 1 · 2 ·… · n (n ≥ 1) as the number of its trailing zeroes multiplied by the first nonzero digit before them.

For example, the essential value of 5! = 120 is 1 · 2 = 2, while the essential value of 12! = 479 001 600 is 2 · 6 = 12.

Given some number v, your task is to determine the smallest number n such that the essential value of n! is exactly v, or report that such n does not exist.

Input Specification

The first line of the input contains the number of test cases T (1 ≤ T ≤ 200 000).

Each test case consists of a single line specifying the essential value v (1 ≤ v ≤ 10¹⁶).

Output Specification

For each test case, print a single line containing the smallest positive integer n such that the essential value of n! is exactly v.

In the cases when such n does not exist, print –1.

Sample Input

1. 7
2. 1
3. 2
4. 4
5. 12
6. 24
7. 1000000000
8. 12345678910

download as text file

Output for Sample Input

1. -1
2. 5
3. 7
4. 12
5. 15
6. 500000009
7. 24691357854

download as text file