【题意】

在以下情况下 $x \ (1 \le x < p)$ 是 $p$ 的原根：

• 条件1： $p$ 是奇素数

• 条件2： 集合$\\{ (x^i \mod p) | 1 \le i \le p-1 \\}$ 等于 集合 $\\{ 1, ..., p-1 \\}$

例如 $x=3，p=7$ 集合为 $\\{ 3, 2, 6, 4, 5, 1\\}$ ，所以 $3$ 是 $7$ 的原根。

给出 $n$ 个正整数 $p_i$ ，求每个正整数 $p_i$ 的原根个数。

【输入格式】

第一行一个数 $n \ (1 < n \le 10000)$；

下来 $n$ 行，一行一个数 $p_i \ (1 \le p_i \le 2*10^7)$ 。

【输出格式】

一行一个数，第 $i$ 行是 $p_i$ 的原根个数（无原根则输出 0）。

【样例输入】

8
1
2
3
4
8
9
10
18

【样例输出】

0
1
1
1
0
2
2
2