我们称一个整数 $n \ge 1$ 是“快乐数”（joyful），如果将数字 $25$ 连接在 $n$ 的右侧后，得到的结果是一个完全平方数。 例如，$2$ 是一个快乐数（因为 $225 = 15^2$），但 $3$ 不是（因为 $325$ 不是完全平方数）。 给定一个整数 $k$，满足 $1 \le k \le 10^9$，求第 $k$ 个快乐数的不同质因数个数。
第一行包含一个整数 $t$，表示测试用例的数量（$1 \le t \le 4 \cdot 10^3$）。 每个测试用例占一行，包含一个整数 $k$（$1 \le k \le 10^9$）。
对于每个测试用例，输出一行，包含一个整数：第 $k$ 个快乐数的不同质因数个数。
样例
输入格式 1
2 1 4
输出格式 1
1 2
输入格式 2
1 1000000000
输出格式 2
7
说明
第一个快乐数是 $2$，它有一个不同的质因数。第四个快乐数是 $20 = 2 \cdot 2 \cdot 5$，它有两个不同的质因数。