J. Joyful Numbers
time limit per test
1 second
memory limit per test
512 mebibytes
input
standard input
output
standard output

We say that an integer $$$n \geq 1$$$ is joyful if, by concatenating the digits $$$25$$$ to the right of $$$n$$$, we get a perfect square. For example, $$$2$$$ is a joyful number (as $$$225 = 15^2$$$) but $$$3$$$ is not (as $$$325$$$ is not a perfect square).

Given an integer $$$k$$$ such that $$$1 \leq k \leq 10^9$$$, count the number of distinct prime factors of the $$$k$$$-th joyful number.

Input

The first line contains one integer $$$t$$$, the number of test cases ($$$1 \leq t \leq 4 \cdot 10^3$$$).

Each test case is given on a separate line containing an integer $$$k$$$ ($$$1 \leq k \leq 10^9$$$).

Output

For each test case, print a line with a single integer: the number of distinct prime factors of the $$$k$$$-th joyful number.

Examples
Input
2
1
4
Output
1
2
Input
1
1000000000
Output
7
Note

The first joyful number is $$$2$$$, which has one distinct prime factor. The fourth joyful number is $$$20 = 2 \cdot 2 \cdot 5$$$, which has two distinct prime factors.