|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||0||0||0||0.000%|
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.
2 1 4
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.