Tenka1 Programmer Contest - ModularPowerEquation!!

Process the Q queries below.

* You are given two integers A_i and M_i. Determine whether there exists a positive integer K_i not exceeding 2 × 10^{18} such that A_i^{K_i} ≡ K_i (mod M_i), and find one if it exists.

Constraints

* 1 \leq Q \leq 100
* 0 \leq A_i \leq 10^9(1 \leq i \leq Q)
* 1 \leq M_i \leq 10^9(1 \leq i \leq Q)



Examples

Input

4
2 4
3 8
9 6
10 7


Output

4
11
9
2


Input

3
177 168
2028 88772
123456789 987654321


Output

7953
234831584
471523108231963269

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def extgcd(a, b):
	if b == 0:
		return 1
	else:
		(x, y, u, v, k, l) = (1, 0, 0, 1, a, b)
		while l != 0:
			(x, y, u, v) = (u, v, x - u * (k // l), y - v * (k // l))
			(k, l) = (l, k % l)
		return x

def inved(x, m):
	return x % m

def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x

def doubling(n, m, mod):
	y = 1
	base = n
	while m != 0:
		if m % 2 == 1:
			y *= base
			y %= mod
		base *= base
		base %= mod
		m //= 2
	return y

def factorization(n):
	if n == 1:
		return {1: 1}
	else:
		D = {}
		base = n
		p = 2
		while n != 1:
			i = 0
			while n % p == 0:
				i += 1
				n //= p
			if i != 0:
				D[p] = i
			p += 1
			if p * p > base and n != 1:
				D[n] = 1
				break
		return D

def Torshent(n):
	dic = factorization(n)
	S = n
	for i in dic:
		S //= i
		S *= i - 1
	return S

def bin_digits(n):
	cnt = 0
	while n != 0:
		cnt += 1
		n //= 2
	return cnt

def Resque(a, mod):
	if mod == 1:
		return 1
	M = Torshent(mod)
	MM = gcd(M, mod)
	R = Resque(a, MM)
	k = doubling(a, R, mod)
	(m, modmod) = (M // MM, mod // MM)
	Tm = Torshent(modmod)
	invm = doubling(m, Tm - 1, modmod)
	t = (k - R) // MM * invm
	R += t * M
	R %= mod * M // MM
	R += mod * M // MM
	return R
Q = int(input())
for i in range(Q):
	(A, M) = map(int, input().split())
	if M == 1:
		print(1)
	else:
		R = Resque(A, M)
		print(R)


from math import gcd

def get_sieve_of_eratosthenes_new(n):
	import math
	if not isinstance(n, int):
		raise TypeError('n is int type.')
	if n < 2:
		raise ValueError('n is more than 2')
	prime = []
	limit = math.sqrt(n)
	data = [i + 1 for i in range(1, n)]
	while True:
		p = data[0]
		if limit <= p:
			return prime + data
		prime.append(p)
		data = [e for e in data if e % p != 0]
prime = get_sieve_of_eratosthenes_new(32000)

def euler_phi(n):
	res = n
	for x in prime:
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def biggcd(n, m):
	g = gcd(n, m)
	res = g
	count = 2
	while True:
		test = gcd(g ** count, m)
		if test > res:
			res = test
			count += 1
		else:
			break
	return res

def solve(a, m, n):
	if gcd(a, m) == 1:
		if m == 1:
			return 1
		phi = euler_phi(m)
		G = gcd(phi, m)
		r0 = solve(a, G, n)
		mod = m * phi // G
		return ((pow(a, n * r0, mod) - n * r0) % mod // G * pow(n * phi // G, phi - 1, m) * phi + r0) % mod
	else:
		big = biggcd(a, m)
		k0 = solve(a, m // big, n * big)
		return big * k0
for i in range(int(input())):
	(A, M) = map(int, input().split())
	print(solve(A, M, 1))


from math import gcd

def euler_phi(n):
	res = n
	for x in range(2, int(n ** 0.5) + 2):
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def biggcd(n, m):
	g = gcd(n, m)
	res = g
	count = 2
	while gcd(g ** count, m) > res:
		res = gcd(g ** count, m)
		count += 1
	return res

def solve(a, m, n):
	if gcd(a, m) == 1:
		if m == 1:
			return 1
		phi = euler_phi(m)
		G = gcd(phi, m)
		r0 = solve(a, G, n)
		mod = m * phi // G
		return ((pow(a, n * r0, mod) - n * r0) % mod // G * pow(n * phi // G, phi - 1, m) * phi + r0) % mod
	big = biggcd(a, m)
	k0 = solve(a, m // big, n * big)
	return big * k0
for i in range(int(input())):
	(A, M) = map(int, input().split())
	print(solve(A, M, 1))