

Valuable FactorialLet 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 SpecificationThe 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^{16}). Output SpecificationFor 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
Output for Sample Input


University of Debrecen; Faculty of Informatics; v. 03/01/2019 