题目描述
Given n and m, calculate 1^{1} + 2^{2} + 3^{3} + ... + n^{n} modulo m.
------ Input ------
The first line contains 1 ≤ t ≤ 10, the number of test cases. Then the test case definitions follow. Each test case is of the form: 1 ≤ n 10^{18}, 1 ≤ m ≤ 200000
------ Output ------
For each test case simply write a single line containing the answer to the problem.
----- Sample Input 1 ------
6
1 100000
2 100000
3 100000
4 100000
5 100000
6 100000
----- Sample Output 1 ------
1
5
32
288
3413
50069
输入格式
见题面
输出格式
见题面
样例输入
6
1 100000
2 100000
3 100000
4 100000
5 100000
6 100000
样例输出
1
5
32
288
3413
50069