In mathematics, a rational number is any number that can be expressed as the quotient or fraction p/q of two integers, a numerator p and a non-zero denominator q

The decimal expansion of a rational number always either terminates after a finite number of digits or begins to repeat the same finite sequence of digits over and over. Moreover, any repeating or terminating decimal represents a rational number.

you are provided with two integers p=1 and q such that 0<q<10^1000 you have to check whether its expansion is repeating or terminating

INPUT

first line will provide number of test cases t

next t lines will provide different values of q

note - q may have preceding zeros

OUTPUT

t lines include output

if it is terminating then output the number of digits after decimal (for example 0.01 outputs 2)

if it is repeating then output must be 0 (for example 0.33333...... outputs 0)

CONSTRAINTS

$1 \leq t \leq 1000$

$1 \leq q \leq$ 10^1000