21069번 - Joyful Numbers 다국어

문제

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.

입력

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$).

출력

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

제한

힌트

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.