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.

If it is terminating then output the number of digits after decimal. If it is repeating then output must be 0.

Input Format-

First line will provide number number of test cases T where 0<T<1000.

Next T lines will provide different values of q.

Output Format-

Next 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)