You are given several queries. Each query consists of three integers $p$, $q$ and $b$. You need to answer whether the result of $p/q$ in notation with base $b$ is a finite fraction.

A fraction in notation with base $b$ is finite if it contains finite number of numerals after the decimal point. It is also possible that a fraction has zero numerals after the decimal point.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of queries.

Next $n$ lines contain queries, one per line. Each line contains three integers $p$, $q$, and $b$ ($0 \le p \le 10^{18}$, $1 \le q \le 10^{18}$, $2 \le b \le 10^{18}$). All numbers are given in notation with base $10$.


-----Output-----

For each question, in a separate line, print Finite if the fraction is finite and Infinite otherwise.


-----Examples-----
Input
2
6 12 10
4 3 10

Output
Finite
Infinite

Input
4
1 1 2
9 36 2
4 12 3
3 5 4

Output
Finite
Finite
Finite
Infinite



-----Note-----

$\frac{6}{12} = \frac{1}{2} = 0,5_{10}$

$\frac{4}{3} = 1,(3)_{10}$

$\frac{9}{36} = \frac{1}{4} = 0,01_2$

$\frac{4}{12} = \frac{1}{3} = 0,1_3$

Difficulty: MEDIUM_HARD
Tags: Mathematics

Implementation

Starter code:

Solutions:
sy = 'Finite'
sn = 'Infinite'
n = int(input())
result = ['' for i in range(n)]
for i in range(n):
	(p, q, b) = list(map(int, input().split()))
	if p * pow(b, 60, q) % q:
		result[i] = sn
	else:
		result[i] = sy
print('\n'.join(result))


n = int(input())
ans = []
while n:
	n += -1
	(p, q, b) = map(int, input().split())
	if p * pow(b, 64, q) % q:
		ans.append('Infinite')
	else:
		ans.append('Finite')
for _ in ans:
	print(_)


import sys

def binpow(a, n, p):
	res = 1
	while n > 0:
		if n % 2 == 1:
			res = res * a % p
		a = a * a % p
		n >>= 1
	return res

def main():
	result = []
	t = int(sys.stdin.readline())
	for line in sys.stdin.readlines():
		(p, q, b) = map(int, line.split())
		for i in range(6):
			b = b * b % q
		result.extend(list('Finite\n' if p * b % q == 0 else list('Infinite\n')))
	sys.stdout.write(''.join(result))
main()


import sys
input()
out = []
for line in sys.stdin:
	(p, q, b) = map(int, line.split())
	out.append('Infinite' if p * pow(b, 64, q) % q else 'Finite')
sys.stdout.write('\n'.join(out))


import sys
input()
out = []
for line in sys.stdin:
	(p, q, b) = [int(x) for x in line.split()]
	out.append(['Finite', 'Infinite'][bool(p * pow(b, 60, q) % q)])
print('\n'.join(out))


import sys
input = sys.stdin.readline
t = int(input())
res = []
for _ in range(t):
	(p, q, b) = map(int, input().split())
	if p * pow(b, 64, q) % q != 0:
		res.append('Infinite')
	else:
		res.append('Finite')
print('\n'.join(res))


input()
print('\n'.join(['Infinite' if p * pow(b, 99, q) % q else 'Finite' for (p, q, b) in map(lambda l: map(int, l.split()), __import__('sys').stdin.readlines())]))


from math import gcd
ans = []
for _ in range(int(input())):
	(p, q, b) = map(int, input().split())
	q //= gcd(p, q)
	if pow(b, 100, q) == 0:
		ans.append('Finite')
	else:
		ans.append('Infinite')
print('\n'.join(ans))


print('\n'.join([(lambda p, q, b: 'Infinite' if p * pow(b, 99, q) % q else 'Finite')(*map(int, input().split())) for _ in range(int(input()))]))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

def main():
	T = int(input())
	for _ in range(T):
		(p, q, b) = list(map(int, input().split()))
		g = gcd(p, q)
		q //= g
		(r, a, n) = (1, b, 64)
		while n:
			if n & 1:
				r = r * a % q
			a = a * a % q
			n >>= 1
		print('Finite' if r == 0 else 'Infinite')
main()


import os
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

def lii():
	return list(map(int, input().split()))

def ii():
	return int(input())
from math import gcd
t = ii()
for _ in range(t):
	(p, q, b) = lii()
	g = gcd(p, q)
	q = q // g
	x = gcd(b, q)
	while x != 1:
		while q % x == 0:
			q //= x
		x = gcd(b, q)
	if q == 1:
		print('Finite')
	else:
		print('Infinite')


import sys

def main():
	n = int(input())
	ans = []
	for i in range(n):
		(p, q, b) = map(int, input().split(' '))
		t = pow(b, 111, q)
		if p * t % q == 0:
			ans.append('Finite')
		else:
			ans.append('Infinite')
	print('\n'.join(ans))
main()


import sys
import math
ini = lambda : int(sys.stdin.readline())
inl = lambda : [int(x) for x in sys.stdin.readline().split()]

def solve():
	(p, q, b) = inl()
	if p == 0:
		return True
	g = math.gcd(p, q)
	p //= g
	q //= g
	if q == 1:
		return True
	for i in range(6):
		b = b * b % q
		if b == 0:
			return True
	return False
n = ini()
for i in range(n):
	print(['Infinite', 'Finite'][solve()])


import sys
import math

def readInts():
	return [int(x) for x in sys.stdin.readline().split()]

def readInt():
	return int(sys.stdin.readline())

def print(x):
	sys.stdout.write(str(x) + '\n')

def solve():
	n = readInt()
	for _ in range(n):
		(p, q, b) = readInts()
		if p * pow(b, 64, q) % q != 0:
			print('Infinite')
		else:
			print('Finite')

def main():
	t = 1
	for _ in range(t):
		solve()
main()


ans = [(lambda p, q, b: 'Infinite' if p * pow(b, 99, q) % q else 'Finite')(*list(map(int, input().split()))) for _ in range(int(input()))]
for _ in ans:
	print(_)


n = int(input())
a = (map(int, input().split()) for _ in range(n))
print('\n'.join((('Finite', 'Infinite')[pow(b, 64, q) * p % q > 0] for (p, q, b) in a)))


from sys import stdin
(_, *l) = stdin.read().splitlines()
for (i, s) in enumerate(l):
	(p, q, b) = map(int, s.split())
	l[i] = 'Infinite' if p * pow(b, 64, q) % q else 'Finite'
print('\n'.join(l))


import sys
input()
for line in sys.stdin:
	(p, q, b) = [int(x) for x in line.split()]
	sys.stdout.write('Infinite\n' if p * pow(b, 64, q) % q else 'Finite\n')


n = int(input())
s = ''
for i in range(n):
	(p, q, b) = map(int, input().split())
	for i in range(6):
		b = b * b % q
	if p * b % q:
		s += 'Infinite\n'
	else:
		s += 'Finite\n'
print(s)


from sys import stdout, stdin, setrecursionlimit
from bisect import insort, bisect_right, bisect_left
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def primeNums():
	N = 10 ** 5
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
t = int(input())
res = []
for _ in range(t):
	(p, q, b) = map(int, input().split())
	g = gcd(p, q)
	q = q // g
	x = gcd(b, q)
	while x != 1:
		while q % x == 0:
			q //= x
		x = gcd(b, q)
	if q == 1:
		output('Finite')
	else:
		output('Infinite')


n = int(input())
ans = ''
while n > 0:
	(p, q, b) = list(map(int, input().split(' ')))
	for i in range(6):
		b = b * b % q
	if b * p % q == 0:
		ans += 'Finite\n'
	else:
		ans += 'Infinite\n'
	n -= 1
print(ans)


from sys import stdin, stdout
n = int(stdin.readline())
s = ''
for i in range(n):
	(p, q, b) = map(int, input().split())
	for i in range(6):
		b = b * b % q
	if p * b % q:
		s += 'Infinite\n'
	else:
		s += 'Finite\n'
print(s)


print('\n'.join((('F', 'Inf')[pow(b, 64, q) * p % q > 0] + 'inite' for (p, q, b) in (map(int, input().split()) for _ in [0] * int(input())))))


s = ''
for i in range(int(input())):
	(a, b, d) = map(int, input().split())
	for i in range(6):
		d = d * d % b
	if d * a % b:
		s += 'Infinite\n'
	else:
		s += 'Finite\n'
print(s)


import os, sys, atexit
from io import BytesIO, StringIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
_OUTPUT_BUFFER = StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
n = int(input())
while n:
	n += -1
	(p, q, b) = map(int, input().split())
	x = lambda p, q, b: 'Infinite' if p * pow(b, 99, q) % q else 'Finite'
	print(x(p, q, b))


import sys
from fractions import gcd

def is_finite(p, q, b):
	return not p * pow(b, 64, q) % q
input()
print('\n'.join(('Finite' if is_finite(*map(int, line.split())) else 'Infinite' for line in sys.stdin.readlines())))


def solve():
	for __ in range(int(input())):
		(p, q, b) = tuple(map(int, input().split()))
		yield ('Infinite' if p * pow(b, 63, q) % q else 'Finite')
print('\n'.join(solve()))


sy = 'Finite'
sn = 'Infinite'
n = int(input())
result = ['' for i in range(n)]
for i in range(n):
	(p, q, b) = list(map(int, input().split()))
	for j in range(4):
		b *= b
		b *= b
		b %= q
	if p * b % q:
		result[i] = sn
	else:
		result[i] = sy
print('\n'.join(result))


import sys

def main():
	n = int(input())
	ans = []
	while n:
		n += -1
		(p, q, b) = map(int, input().split())
		if p * pow(b, 99, q) % q:
			ans.append('Infinite')
		else:
			ans.append('Finite')
	for _ in ans:
		print(_)
main()


input()
print('\n'.join(map(lambda x: (lambda p, q, b: 'Infinite' if p * pow(b, 60, q) % q else 'Finite')(*x), map(lambda l: map(int, l.split()), __import__('sys').stdin.readlines()))))


import sys
input()
out = []
for line in sys.stdin:
	(p, q, b) = [int(x) for x in line.split()]
	out.append('Infinite' if p * pow(b, 64, q) % q else 'Finite')
print('\n'.join(out))


def solve(p, q, b):
	if p * pow(b, 64, q) % q == 0:
		return 1
	else:
		return 0

def main():
	n = int(input())
	s = ''
	for i in range(n):
		(p, q, b) = [int(x) for x in input().split()]
		if solve(p, q, b) == True:
			s += 'Finite\n'
		else:
			s += 'Infinite\n'
	print(s)
main()


n = int(input())
result = ''
while n:
	io = input().split(' ')
	p = int(io[0])
	q = int(io[1])
	b = int(io[2])
	if p * pow(b, 60, q) % q:
		result += 'Infinite\n'
	else:
		result += 'Finite\n'
	n -= 1
print(result)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
import math
for i in range(n):
	(p, q, b) = map(int, input().split())
	g = math.gcd(p, q)
	p //= g
	q //= g
	if p == 0 or q == 1:
		print('Finite')
		continue
	g = math.gcd(q, b)
	while g != 1:
		q //= g
		b = g
		g = math.gcd(q, b)
	if q != 1:
		print('Infinite')
	else:
		print('Finite')


from math import gcd
import os
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

def vvod():
	return int(input())

def vvod1():
	return map(int, input().split())
n = vvod()
for i in range(n):
	(p, q, k) = vvod1()
	dele = gcd(p, q)
	q = q // dele
	dele = gcd(k, q)
	while dele != 1:
		while q % dele == 0:
			q = q // dele
		dele = gcd(k, q)
	if q == 1:
		print('Finite')
	else:
		print('Infinite')


def mod(b, q):
	for i in range(6):
		b = b * b % q
	return b
n = int(input())
s = ''
for i in range(n - 1):
	(p, q, b) = list(map(int, input().split()))
	if p * mod(b, q) % q:
		s += 'Infinite\n'
	else:
		s += 'Finite\n'
(p, q, b) = list(map(int, input().split()))
if p * mod(b, q) % q:
	s += 'Infinite'
else:
	s += 'Finite'
print(s)