You are given 2 integers a and b. Let a number be defined as
$a+b\sqrt{5}$
. As we know  
$a+b\sqrt{5}$
will be an irrational number when b is non-zero. In this problem, we call it the AC number. We define
$\left[x\right]_{m} =xmod m$
 (where x an integer)

 and the operation
$\otimes$
  on AC number as:
$(a+b{\sqrt{5}})\otimes(c+d{\sqrt{5}})=[a c+5b d]_{m}+[a d+b c]_{m}{\sqrt{5}}$
This problem is to find the smallest positive integer n, such that:
$\underbrace{(a+b\sqrt5)\otimes(a+b\sqrt5)\cdots\otimes(a+b\sqrt5)}_{n\text{times}}=1$
We call the integer n as period. You are given a, b and m. Can you figure out the period?

Input Format 

The first line of the input contains a single integer T denoting the number of test-cases. 

T lines follow, each containing 3 integers - a, b and m separated by a single space. 

Output Format 

Output the Period if it exists, otherwise output "-1" (quotes only for reference)

Constraints 

1 ≤ T ≤ 300 

5 ≤ m ≤ 10^{7} 

0 ≤ a, b < m

Sample Input #00

4
0 0 13
1 0 7
3 0 10007
1 1 19

Sample Output #00

-1
1
5003
18

Explanation #00   

For the 1st test-case, no amount of operation ⊗ on a = 0, b = 0 gives 1 on the RHS. Hence the answer is -1. 

When a = 1, b = 0, we have 1 for n = 1. 

On repeated operations, the third and the fourth testcases sum to 1 for n = 5003 and n = 18 respectively. $. As we know  will be an irrational number when b is non-zero. In this problem, we call it the AC number. We define  (where x an integer) and the operation  on AC number as:This problem is to find the smallest positive integer n, such that:We call the integer n as period. You are given a, b and m. Can you figure out the period?Input Format The first line of the input contains a single integer T denoting the number of test-cases. T lines follow, each containing 3 integers - a, b and m separated by a single space. Output Format Output the Period if it exists, otherwise output "-1" (quotes only for reference)Constraints 1 ≤ T ≤ 300 5 ≤ m ≤ 10^{7} 0 ≤ a, b < mSample Input #0040 0 131 0 73 0 100071 1 19Sample Output #00-11500318Explanation #00   For the 1st test-case, no amount of operation ⊗ on a = 0, b = 0 gives 1 on the RHS. Hence the answer is -1. When a = 1, b = 0, we have 1 for n = 1. On repeated operations, the third and the fourth testcases sum to 1 for n = 5003 and n = 18 respectively. will be an irrational number when b is non-zero. In this problem, we call it the AC number. We define  (where x an integer) and the operation  on AC number as:This problem is to find the smallest positive integer n, such that:We call the integer n as period. You are given a, b and m. Can you figure out the period?Input Format The first line of the input contains a single integer T denoting the number of test-cases. T lines follow, each containing 3 integers - a, b and m separated by a single space. Output Format Output the Period if it exists, otherwise output "-1" (quotes only for reference)Constraints 1 ≤ T ≤ 300 5 ≤ m ≤ 10^{7} 0 ≤ a, b < mSample Input #0040 0 131 0 73 0 100071 1 19Sample Output #00-11500318Explanation #00   For the 1st test-case, no amount of operation ⊗ on a = 0, b = 0 gives 1 on the RHS. Hence the answer is -1. When a = 1, b = 0, we have 1 for n = 1. On repeated operations, the third and the fourth testcases sum to 1 for n = 5003 and n = 18 respectively.$
. As we know  will be an irrational number when b is non-zero. In this problem, we call it the AC number. We define 

 (where x an integer)

 and the operation  on AC number as:

This problem is to find the smallest positive integer n, such that:

We call the integer n as period. You are given a, b and m. Can you figure out the period?

Input Format 

The first line of the input contains a single integer T denoting the number of test-cases. 

T lines follow, each containing 3 integers - a, b and m separated by a single space. 

Output Format 

Output the Period if it exists, otherwise output "-1" (quotes only for reference)

Constraints 

1 ≤ T ≤ 300 

5 ≤ m ≤ 10^{7} 

0 ≤ a, b < m

Sample Input #00

4
0 0 13
1 0 7
3 0 10007
1 1 19

Sample Output #00

-1
1
5003
18

Explanation #00   

For the 1st test-case, no amount of operation ⊗ on a = 0, b = 0 gives 1 on the RHS. Hence the answer is -1. 

When a = 1, b = 0, we have 1 for n = 1. 

On repeated operations, the third and the fourth testcases sum to 1 for n = 5003 and n = 18 respectively.

Difficulty: MEDIUM_HARD
Tags: Number theory

Starter code:

Solutions:
def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())

	def mul(p1, p2):
		(a1, b1) = p1
		(a2, b2) = p2
		return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

	def norm(p):
		(a, b) = p
		return (a * a - b * b * 5) % m

	def inv(p):
		assert norm(p) == 1
		(a, b) = p
		return (a, -b)
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())

	def mul(p1, p2):
		(a1, b1) = p1
		(a2, b2) = p2
		return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

	def norm(p):
		(a, b) = p
		return (a * a - b * b * 5) % m

	def inv(p):
		assert norm(p) == 1
		(a, b) = p
		return (a, -b)
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L = [0]
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total

def is_miller_rabin(x, num_tests=3):
	k = x - 1
	e = 0
	while k % 2 == 0:
		e += 1
		k //= 2
	tests = [False for _ in range(0, num_tests)]
	A = [2, 3, 5]
	for j in range(3, num_tests):
		A.append(random.randint(7, x - 1))
	if x < 2047:
		num_tests = 1
	elif x < 1373653:
		num_tests = 2
	elif x < 25326001:
		num_tests = 3
	for i in range(0, num_tests):
		ak = pow_mod(A[i], k, x)
		if ak == 1:
			tests[i] = True
		else:
			for j in range(0, e):
				if ak == x - 1:
					tests[i] = True
				ak = ak * ak % x
	for i in range(0, num_tests):
		if not tests[i]:
			return False
	return True

def factor(n, PL):
	sqrt = int(pow(n, 0.5)) + 1
	factor_list = []
	if not PL:
		PL = prime_list(sqrt)
	for p in PL:
		if n % p == 0:
			elet = [p, 0]
			while not n % p:
				n //= p
				elet[1] += 1
			factor_list.append(elet)
	if n != 1:
		if is_miller_rabin(n):
			factor_list.append([n, 1])
	return factor_list

def is_prime(x, L=[]):
	sqrt = int(pow(x, 0.5)) + 1
	PL = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 16, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	if not L:
		if x < 210:
			if x in PL:
				return True
			else:
				return False
		else:
			for p in PL:
				if x % p == 0:
					return False
			for i in range(1, sqrt // 210 + 1):
				for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
					if x % (210 * i + j) == 0:
						return False
		return True
	elif x != 0 and x != 1:
		j = 0
		while j < len(L) and L[j] <= sqrt:
			if x % L[j] == 0:
				return False
			j += 1
	else:
		return False
	return True

def prime_list(n):
	L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	for k in range(1, n // 210):
		for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
			if is_prime(210 * k + j, L):
				L.append(210 * k + j)
	k = n // 210
	for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
		if is_prime(210 * k + j, L) and 210 * k + j <= n:
			L.append(210 * k + j)
	return L

def euler_totient_with_factors(n, factors):
	for ar_elet in factors:
		n //= ar_elet[0]
		n *= ar_elet[0] - 1
	return n

def augmeted_mult(a, b, c, d):
	return (a * c + 5 * b * d, a * d + b * c)

def augmented_pow_mod(a, b, p, m):
	p_bits = bitize(p)
	x = 1
	y = 0
	pa = a % m
	pb = b % m
	for i in range(0, len(p_bits)):
		if p_bits[i]:
			(x, y) = augmeted_mult(pa, pb, x, y)
			x %= m
			y %= m
		(pa, pb) = augmeted_mult(pa, pb, pa, pb)
		pa %= m
		pb %= m
	return (x, y)

def compute_order(a, b, m, PL):
	m_factors = factor(m, PL)
	phi_m = euler_totient_with_factors(m, m_factors)
	phi_m_factors = factor(phi_m, PL)
	(x, y) = augmented_pow_mod(a, b, phi_m, m)
	order_power = phi_m
	if x == 1 and y == 0:
		for i in range(0, len(phi_m_factors)):
			j = 0
			while j < phi_m_factors[i][1] and (1, 0) == augmented_pow_mod(a, b, order_power // phi_m_factors[i][0], m):
				order_power //= phi_m_factors[i][0]
				j += 1
		return order_power
	else:
		if (1, 0) == augmented_pow_mod(a, b, (m + 1) * phi_m, m):
			order_power = (m + 1) * phi_m
			phi_m_factors = factor((m + 1) * phi_m, PL)
			for i in range(0, len(phi_m_factors)):
				j = 0
				while j < phi_m_factors[i][1] and (1, 0) == augmented_pow_mod(a, b, order_power // phi_m_factors[i][0], m):
					order_power //= phi_m_factors[i][0]
					j += 1
			return order_power
		return -1
PL = prime_list(50000)
T = int(input())
for _ in range(0, T):
	(a, b, m) = [int(i) for i in input().split()]
	print(compute_order(a, b, m, PL))


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())

	def mul(p1, p2):
		(a1, b1) = p1
		(a2, b2) = p2
		return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

	def norm(p):
		(a, b) = p
		return (a * a - b * b * 5) % m

	def inv(p):
		assert norm(p) == 1
		(a, b) = p
		return (a, -b)
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())

	def mul(p1, p2):
		(a1, b1) = p1
		(a2, b2) = p2
		return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

	def norm(p):
		(a, b) = p
		return (a * a - b * b * 5) % m

	def inv(p):
		assert norm(p) == 1
		(a, b) = p
		return (a, -b)
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


import sys, math, itertools
from collections import Counter

def prime_factorization(x):
	counts = Counter()
	while x != 1:
		isPrime = True
		for p in range(2, 1 + int(math.sqrt(x))):
			if x % p == 0:
				counts[p] += 1
				x //= p
				isPrime = False
				break
		if isPrime:
			counts[x] += 1
			break
	return counts

def power(a, n, mult, unity):
	prod = unity
	pwr = a
	while n != 0:
		if n % 2 != 0:
			prod = mult(prod, pwr)
		n >>= 1
		if n == 0:
			break
		pwr = mult(pwr, pwr)
	return prod

def get_period(a, nz, mult, unity):
	if a == unity:
		return 1
	pf = prime_factorization(nz)
	pf = [(p, c) for (p, c) in pf.items()]
	pf.sort()
	emaxes = tuple([range(c + 1) for (_, c) in pf])
	divs = []
	for exps in itertools.product(*emaxes):
		s = sum(exps)
		if s == 0:
			continue
		divs.append((s, exps))
	divs.sort()
	for (_, exps) in divs:
		x = a
		for ((p, _), k) in zip(pf, exps):
			if k == 0:
				continue
			for _ in range(k):
				x = power(x, p, mult, unity)
		if x == unity:
			e = 1
			for ((p, _), k) in zip(pf, exps):
				if k == 0:
					continue
				e *= p ** k
			return e
	return -1

def getPeriod(a, b, m):
	nz = m * m - 1

	def red(x):
		y = x % m
		if y < 0:
			y += m
		return y

	def norm(x):
		(a, b) = x
		return red(a * a - 5 * b * b)

	def mult(x, y):
		(a, b) = x
		(c, d) = y
		return (red(a * c + 5 * b * d), red(a * d + b * c))
	if math.gcd(norm((a, b)), m) != 1:
		return -1
	per = get_period((a, b), nz, mult, (1, 0))
	return per

def main():
	ncases = int(sys.stdin.readline())
	for _ in range(ncases):
		line = sys.stdin.readline().strip()
		(a, b, m) = list(map(int, line.strip().split()))
		print(getPeriod(a, b, m))
main()


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())

	def mul(p1, p2):
		(a1, b1) = p1
		(a2, b2) = p2
		return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

	def norm(p):
		(a, b) = p
		return (a * a - b * b * 5) % m

	def inv(p):
		assert norm(p) == 1
		(a, b) = p
		return (a, -b)
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


from collections import *
from itertools import *
from math import *
import os
from random import *
import re
import sys

def debug(*args, **kwargs):
	pass
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]

def period(a, b, m):
	fac = factorize(m)
	n = Counter()
	for (p, k) in fac.items():
		debug('factor of m', p, k)
		q = p ** k
		if p == 2:
			if k == 1:
				if a & b & 1 == 1:
					return -1
				if n[2] == 0:
					n[2] = 1
				continue
			e = Counter({2: k - 1})
		elif p == 3:
			e = Counter({3: k - 1, 2: 3})
		elif p == 5:
			e = Counter({5: k, 2: 2})
		else:
			j = jacobi(5, p)
			debug('jacobi', j)
			assert j != 0
			e = Counter({p: k})
			e.update(factorize(p - 1))
			if j < 0:
				e.update(factorize(p + 1))
		n |= e
		del e
	return lagrange(a, b, m, n)

def lcm(a, b):
	g = gcd(a, b)
	if g == a:
		return b
	if g == b:
		return a
	if g == 1:
		return a * b
	return a // g * b

def lagrange(a, b, m, fac):
	result = 1
	debug('lagrange', a, b, m, fac)
	n = prod((p ** k for (p, k) in fac.items()))
	if (1, 0) != powmod(a, b, n, m):
		return -1
	for (p, k) in fac.items():
		for i in range(k, 0, -1):
			if (1, 0) == powmod(a, b, n // p ** i, m):
				debug(f' {p}**{k - i}')
				result *= p ** (k - i)
				break
		else:
			debug(f' {p}**{k}')
			result *= p ** k
	debug('  -->', result)
	return result

def powmod(a, b, n, m):
	result = (1, 0)
	x = (a, b)
	while n:
		if n & 1:
			result = mul(result, x, m)
		n >>= 1
		x = mul(x, x, m)
	return result

def mul(x, y, m):
	return ((x[0] * y[0] + 5 * x[1] * y[1]) % m, (x[0] * y[1] + x[1] * y[0]) % m)

def jacobi(n, k):
	n %= k
	t = 1
	while n != 0:
		while n & 1 == 0:
			n >>= 1
			r = k & 7
			if r == 3 or r == 5:
				t = -t
		(n, k) = (k, n)
		if n & k & 3 == 3:
			t = -t
		n %= k
	return t if k == 1 else 0

def factorize(m):
	fac = Counter()
	for p in primes:
		if p > m:
			break
		e = 0
		while 0 == m % p:
			e += 1
			m //= p
		if e:
			fac[p] = e
		if m == 1:
			break
	else:
		fac[m] = 1
	return fac

def prod(iterable, start=1):
	result = start
	for i in iterable:
		result *= i
	return result
T = int(input())
for t in range(T):
	(a, b, m) = map(int, input().strip().split())
	print(period(a, b, m))


def my_pow(a, b, exp, m):
	a0 = 1
	b0 = 0
	while exp > 0:
		if exp % 2 == 1:
			temp_a = a * a0 + 5 * b * b0
			temp_b = a * b0 + b * a0
			a0 = temp_a % m
			b0 = temp_b % m
		exp = exp // 2
		temp_a = a ** 2 + 5 * b ** 2
		temp_b = 2 * a * b
		a = temp_a % m
		b = temp_b % m
	return (a0, b0)

def check(a, b, m, exp):
	save_exp = exp
	a0 = 1
	b0 = 0
	while exp > 0:
		if exp % 2 == 1:
			temp_a = a * a0 + 5 * b * b0
			temp_b = a * b0 + b * a0
			a0 = temp_a % m
			b0 = temp_b % m
		exp = exp // 2
		temp_a = a ** 2 + 5 * b ** 2
		temp_b = 2 * a * b
		a = temp_a % m
		b = temp_b % m
	if a0 == 1 and b0 == 0:
		return save_exp
	extra = 0
	a = a0
	b = b0
	while a != 1 or b != 0:
		temp_a = a * a0 + 5 * b * b0
		temp_b = a * b0 + b * a0
		a = temp_a % m
		b = temp_b % m
		extra += 1
	return extra * save_exp

def is_prime(k):
	small = [2, 3, 5, 7]
	if k in small:
		return True
	if k % 2 == 0:
		return False
	odd = k - 1
	e = 0
	while odd % 2 == 0:
		e += 1
		odd = odd // 2
	for p in small:
		num = pow(p, odd, k)
		check = False
		if num == 1 or num == k - 1:
			continue
		for i in range(e):
			num = pow(num, 2, k)
			if num == k - 1:
				check = True
				break
			if num == 1:
				return False
		if not check and num != 1:
			return False
	return True
import math

def gcd(a, b):
	while b > 0:
		c = a % b
		a = b
		b = c
	return a

def factor(n):
	if is_prime(n):
		return {n: 1}
	d = dict()
	l = [i for i in range(1, 30) if i % 2 != 0 and i % 3 != 0 and (i % 5 != 0)]
	x = 0
	sq = math.sqrt(n)
	while x * 30 < sq:
		arr = [i + 30 * x for i in l]
		if x == 0:
			arr.pop(0)
			arr.append(2)
			arr.append(3)
			arr.append(5)
		for div in arr:
			while n % div == 0:
				if div in d:
					d[div] += 1
				else:
					d[div] = 1
				n = n // div
		x += 1
		if n == 1:
			break
	if n != 1:
		d[n] = 1
	return d

def alt_phi(d):
	ans = 1
	for (prime, exp) in d.items():
		if prime == 2:
			ans = ans * pow(prime, 2 * exp - 1)
		elif prime == 5:
			ans = ans * 20 * pow(prime ** 2, exp - 1)
		else:
			ans = ans * (prime ** 2 - 1) * pow(prime ** 2, exp - 1)
	return ans

def order(a, b, m):
	d1 = factor(m)
	d = factor(alt_phi(d1))
	h = alt_phi(d1)
	n = m
	e = h
	for (pi, vi) in d.items():
		e = e // pow(pi, vi)
		(g1, g2) = my_pow(a, b, e, n)
		while g1 != 1 or g2 != 0:
			(g1, g2) = my_pow(g1, g2, pi, n)
			e = e * pi
	return e
for _ in range(int(input())):
	(a, b, m) = list(map(int, input().split(' ')))
	norm = a ** 2 - 5 * b ** 2
	norm = norm % m
	if gcd(norm, m) > 1:
		print(-1)
		continue
	if a % m == 1 and b % m == 0:
		print(1)
		continue
	ans = order(a, b, m)
	print(check(a, b, m, ans))


import math
maxprime = 3200
isprime = [True] * maxprime
primelist = []
for i in range(2, maxprime):
	if isprime[i]:
		primelist.append(i)
		for j in range(i * i, maxprime, i):
			isprime[j] = False

def factor(n):
	curr = n
	toret = dict()
	for p in primelist:
		numreps = 0
		while curr % p == 0:
			numreps += 1
			curr //= p
		if numreps > 0:
			toret[p] = numreps
		if p * p > curr:
			break
	if curr != 1:
		toret[curr] = 1
	return toret
primefacts = dict()

def rt5pow(a, b, e, m):
	currval = [1, 0]
	pow2 = [a, b]
	curr = e
	while curr > 0:
		if curr % 2 == 1:
			currval = [(currval[0] * pow2[0] + 5 * currval[1] * pow2[1]) % m, (currval[0] * pow2[1] + currval[1] * pow2[0]) % m]
		pow2 = [(pow2[0] * pow2[0] + 5 * pow2[1] * pow2[1]) % m, 2 * pow2[0] * pow2[1] % m]
		curr //= 2
	return currval
t = int(input())
for _ in range(t):
	[a, b, m] = list(map(int, input().split(' ')))
	factm = factor(m)
	powfact = dict()
	for p in factm.keys():
		e = factm[p]
		try:
			tolcm = primefacts[p]
		except:
			tolcm = factor(p - 1)
			highfact = factor(p + 1)
			for q in highfact.keys():
				try:
					tolcm[q] = tolcm[q] + highfact[q]
				except:
					tolcm[q] = highfact[q]
			primefacts[p] = tolcm
		if e > 1:
			tolcm[p] = 2 * e
		for q in tolcm.keys():
			f = tolcm[q]
			try:
				powfact[q] = max(powfact[q], tolcm[q])
			except:
				powfact[q] = tolcm[q]
	maxpow = 1
	for p in powfact.keys():
		e = powfact[p]
		maxpow *= pow(p, e)
	if rt5pow(a, b, maxpow, m) != [1, 0]:
		print(-1)
	else:
		currpow = maxpow
		for p in powfact.keys():
			while currpow % p == 0 and rt5pow(a, b, currpow // p, m) == [1, 0]:
				currpow //= p
		print(currpow)


from itertools import compress
from collections import defaultdict
import sys

def read_one():
	return sys.stdin.readline().strip()

def read_spaced():
	return sys.stdin.readline().strip().split()

def read_spaced_int():
	return map(int, read_spaced())

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def rwh_primes_iter(n):
	half = n >> 1
	sieve = bytearray([True]) * half
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i >> 1]:
			sieve[i * i >> 1::i] = bytearray((n - i * i - 1) // (2 * i) + 1)
	return [2, *compress(range(3, n, 2), sieve[1:])]

def factorize(n):
	fac = []
	for p in primes:
		if p * p > n:
			break
		e = 0
		while n % p == 0:
			n //= p
			e += 1
		if e:
			fac.append((p, e))
	if n > 1:
		fac.append((n, 1))
	return fac

def divisors(factors):
	div = [1]
	for (p, e) in factors:
		div = [p ** f * d for d in div for f in range(e + 1)]
	return sorted(div)

def func(n):
	ans = n
	fac = defaultdict(int)
	for (p, e) in factorize(n):
		fac = defaultdict(int)
		ans = ans // p * (p - 1)
	return ans

def eval_pow(a, b, n, m):
	(u, v) = (1, 0)
	while n:
		if n & 1:
			(u, v) = ((u * a + 5 * b * v) % m, (u * b + a * v) % m)
		(a, b) = ((a ** 2 + 5 * b ** 2) % m, 2 * a * b % m)
		n >>= 1
	return (u, v)
primes = rwh_primes_iter(5 * 10 ** 3)

def prod_quad(X, Y, m):
	return ((X[0] * Y[0] + 5 * X[1] * Y[1]) % m, (X[0] * Y[1] + X[1] * Y[0]) % m)

def solve_prime(a, b, p):
	fac = defaultdict(int)
	fac[p] = 1
	for (q, e) in factorize(p - 1):
		fac[q] += 2 * e
	for (q, e) in factorize(p + 1):
		fac[q] += e
	for d in divisors(fac.items()):
		if eval_pow(a, b, d, p) == (1, 0):
			return d
	raise Exception('Not Found')

def solve_composite(a, b, m):
	ans = 1
	g = (a ** 2 - 5 * b ** 2) % m
	if gcd(g, m) > 1:
		return -1
	for (p, e) in factorize(m):
		ans = p ** (e - 1) * lcm(ans, solve_prime(a, b, p))
	return ans
T = int(read_one())
for _ in range(T):
	(a, b, m) = read_spaced_int()
	print(solve_composite(a, b, m))


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())

	def mul(p1, p2):
		(a1, b1) = p1
		(a2, b2) = p2
		return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

	def norm(p):
		(a, b) = p
		return (a * a - b * b * 5) % m

	def inv(p):
		assert norm(p) == 1
		(a, b) = p
		return (a, -b)
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())

	def mul(p1, p2):
		(a1, b1) = p1
		(a2, b2) = p2
		return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

	def norm(p):
		(a, b) = p
		return (a * a - b * b * 5) % m

	def inv(p):
		assert norm(p) == 1
		(a, b) = p
		return (a, -b)
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())

	def mul(p1, p2):
		(a1, b1) = p1
		(a2, b2) = p2
		return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

	def norm(p):
		(a, b) = p
		return (a * a - b * b * 5) % m

	def inv(p):
		assert norm(p) == 1
		(a, b) = p
		return (a, -b)
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())

	def mul(p1, p2):
		(a1, b1) = p1
		(a2, b2) = p2
		return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

	def norm(p):
		(a, b) = p
		return (a * a - b * b * 5) % m

	def inv(p):
		assert norm(p) == 1
		(a, b) = p
		return (a, -b)
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())

	def mul(p1, p2):
		(a1, b1) = p1
		(a2, b2) = p2
		return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

	def norm(p):
		(a, b) = p
		return (a * a - b * b * 5) % m

	def inv(p):
		assert norm(p) == 1
		(a, b) = p
		return (a, -b)
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)


def euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	q = a // b
	(g, u, v) = euclid(b, a - q * b)
	return (g, v, u - q * v)

def modInverse(a, m):
	(g, u, v) = euclid(a, m)
	assert g == 1
	return u % m

def dpow(x, p, one, mul):
	ret = one
	while p > 0:
		if p % 2 == 1:
			ret = mul(ret, x)
		p //= 2
		x = mul(x, x)
	return ret

def dLog(x, y, one, mul, inv, limit):
	step = 1
	while step * step < limit:
		step += 1
	d = dict()
	invx = inv(x)
	cur = mul(invx, y)
	for i in range(1, step + 1):
		if cur not in d:
			d[cur] = i
		cur = mul(cur, invx)
	ret = limit + 1
	cur = one
	xstep = dpow(x, step, one, mul)
	for i in range(step):
		if cur in d:
			ret = min(ret, step * i + d[cur])
		cur = mul(cur, xstep)
	return -1 if ret == limit + 1 else ret

def mul(p1, p2):
	(a1, b1) = p1
	(a2, b2) = p2
	return ((a1 * a2 + b1 * b2 * 5) % m, (a1 * b2 + a2 * b1) % m)

def norm(p):
	(a, b) = p
	return (a * a - b * b * 5) % m

def inv(p):
	assert norm(p) == 1
	(a, b) = p
	return (a, -b)
tests = int(input())
for test in range(tests):
	(a, b, m) = map(int, input().split())
	x = (a, b)
	xlen = norm(x)
	if euclid(xlen, m)[0] != 1:
		print(-1)
		continue
	plen = dLog(xlen, 1, 1, lambda a, b: a * b % m, lambda a: modInverse(a, m), m)
	x = dpow(x, plen, (1, 0), mul)
	pdir = dLog(x, (1, 0), (1, 0), mul, inv, 10 * m)
	assert plen != -1
	print(plen * pdir)