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: competition

Starter code:

Solutions:
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 = list(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()


input()
print(*['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())], sep='\n')


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


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


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


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)

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)

# python3
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()))


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)

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)


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) 

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()))]))

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))

n = int(input())
ans = ''
while n > 0:
	p, q, b = 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)

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

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()

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')(*list(map(int, input().split()))) for _ in range(int(input()))]))


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(_)


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


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