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

Source: codechef | Difficulty: HARD


Solutions:
def S(a, n, m):
	if n == -1:
		return 0
	if n == 0:
		return 1
	if n == 1:
		return (1 + a) % m
	if n % 2 == 1:
		ans = (1 + a) * S(a * a % m, (n - 1) // 2, m)
	else:
		ans = 1 + a * (1 + a) * S(a * a % m, n // 2 - 1, m)
	return ans % m
for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	s = 0
	e = n // m
	for i in range(1, n % m + 1):
		f = pow(i, e * m + i, m)
		s += f
		s = s % m
	for i in range(2, m + 1):
		a = pow(i, m, m)
		d = S(a, e - 1, m)
		b = pow(i, i, m)
		s += d % m * b % m
		s = s % m
	s += e
	print(s % m)


def p(b, e):
	t = 1
	while e:
		if e & 1:
			t = t * b % mod
		b = b * b % mod
		e >>= 1
	return t

def f(i, e):
	b = p(i, i)
	t = 0
	m = 1
	m2 = p(i, mod)
	while e:
		if e & 1:
			t = (t + m * b % mod) % mod
			m = m * m2 % mod
		b = b * (m2 + 1) % mod
		m2 = m2 * m2 % mod
		e >>= 1
	return t
for _ in range(int(input())):
	(n, mod) = map(int, input().split())
	ans = 0
	for i in range(1, min(n + 1, mod)):
		ans = (ans + f(i, (n + mod - i) // mod)) % mod
	print(ans)