즐거운 수

정수 $n \geq 1$의 오른쪽에 숫자 $25$를 이어 붙여 만든 수가 완전제곱수이면 $n$을 즐거운 수라고 한다. 예를 들어 $2$는 즐거운 수이고($225 = 15^2$), $3$은 아니다($325$는 완전제곱수가 아니다).

$1 \leq k \leq 10^9$인 정수 $k$가 주어질 때, $k$번째 즐거운 수의 서로 다른 소인수의 개수를 구하여라.

첫째 줄에 테스트 케이스의 개수 $t$가 주어진다 ($1 \leq t \leq 4 \cdot 10^3$).

각 테스트 케이스는 정수 $k$ 하나를 포함하는 한 줄로 주어진다 ($1 \leq k \leq 10^9$).

각 테스트 케이스마다 $k$번째 즐거운 수의 서로 다른 소인수의 개수를 한 줄에 출력한다.

첫 번째 즐거운 수는 $2$이고, 서로 다른 소인수가 하나다. 네 번째 즐거운 수는 $20 = 2 \cdot 2 \cdot 5$이고, 서로 다른 소인수가 둘이다.