408334: GYM103098 J 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.

2
1
4

1
2

1
1000000000

7

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.