提示: 欢迎访问OurACM平台。
Problem 2018 计数

Accept: 112    Submit: 450
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

对于方程 x^x = a(mod p), PH想知道对于[0,p-1]内的数,有多少个这样的x满足这个方程。请注意,虽然对于0^0的值有争论,甚至不一定有意义,可是在本题中,PH认为0^0 = 1。

Input

输入数据第一行是一个正整数T,表示数据组数 (T <= 100)

接下来是T组数据,对于每组数据只包含2个正整数 a, p (1 <= a <= 10^1000, 1 <= p <= 10^4)

Output

对于每组数据,输出一个正整数,表示满足方程的x的个数。

Sample Input

3 10000000000000000000000001 5 1 1 1 2

Sample Output

3 1 2

Hint

第一组数据中, x^x = 1(mod 5), 在[0, 4]内,x = 0, x = 1, x= 4均满足条件。 第二组数据中, x^x = 1(mod 1), 在[0,0]内,x = 0 满足条件。 第三组数据中,x^x = 1 (mod 2), 在[0,1]内,x = 0, x = 1满足条件。

Source

FOJ有奖月赛-2011年04月(校赛热身赛)

Submit  Back  Status  Discuss