Solve the programming task below in a Python markdown code block.
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