C. Finite or not?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given several queries. Each query consists of three integers pp, qq and bb. You need to answer whether the result of p/qp/qin notation with base bb is a finite fraction.

A fraction in notation with base bb 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 nn (1≤n≤1051≤n≤105) — the number of queries.

Next nn lines contain queries, one per line. Each line contains three integers pp, qq, and bb (0≤p≤10180≤p≤1018, 1≤q≤10181≤q≤1018, 2≤b≤10182≤b≤1018). All numbers are given in notation with base 1010.

Output

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

Examples
input
Copy 
2
6 12 10
4 3 10
output
Copy 
Finite
Infinite
input
Copy 
4
1 1 2
9 36 2
4 12 3
3 5 4
output
Copy 
Finite
Finite
Finite
Infinite
Note

612=12=0,510612=12=0,510

43=1,(3)1043=1,(3)10

936=14=0,012936=14=0,012

412=13=0,13412=13=0,13

题意：问p/q在b进制下能不能表示为有限位

思路：

若可以转化为有限位，q|p*b^k。分解质因数，p/gcd(q,p)，那么p,q互质。q|p*b^k等价于q|b^k。那么q所有质因数都包含在b里。

本质是唯一分解定理的运用

#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
#define debug puts
using namespace std;
typedef long long ll;

const int N=3e5+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
map<ll,ll> mp;
ll gcd(ll a,ll b){
    if(a<b) swap(a,b);
    return b==0?a:gcd(b,a%b);
}
int main(void){
    ll n,p,q,b;
    cin >>n;
    while(n--){
        scanf("%I64d%I64d%I64d",&p,&q,&b);
        ll GCD=gcd(p,q);
        p/=GCD,q/=GCD;
        while(1){
                GCD=gcd(b,q);
                if(GCD==1)  break;
                while(q%GCD==0) q/=GCD;
        }
        if(q==1)    printf("Finite\n");
        else printf("Infinite\n");
    }
    return 0;
}