### 问题描述 对于方程 $(x^{x} )\times (x+1)= a(mod$ $p)$，PH 想知道对于 $\left[0,p-1\right]$ 内的数，有多少个这样的 $x$ 满足这个方程。请注意，虽然对于 $0^{0}$ 的值有争论，甚至不一定有意义，可是在本题中，PH 认为 $0^{0} = 1$。 ### 输入格式 输入数据第一行是一个正整数 $T(T\le 100)$，表示数据组数。 接下来是 $T$ 组数据，对于每组数据只包含 $2$ 个正整数 $a, p (1 \le a\le 10^{1000}, 1\le p\le 10^4)$。 ### 输出格式 对于每组数据，输出一个正整数，表示满足方程的 $x$ 的个数。 ### 样例输入 ```text 3 10000000000000000000000001 5 1 1 1 2 ``` ### 样例输出 ```text 1 1 1 ``` ### 说明 $x=y (mod$ $p)$ 表示 $x$%$p$ 等于 $y$%$p$。 取模运算的性质： （1）$(a+b)$%$c=(a$%$c+b$%$c)$%$c$，（2）$(ab)$%$c=(a$%$c)(b$%$c)$%$c$。