Codeforces Round #483 (Div. 2) C. Finite or not?

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

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

题意：p/q能否表示为b进制下的有限小数形式,即1/q能否表示为b进制下的有限小数形式，类似十进制小数转二进制，

如0.125，小数乘以进制取整数0，小数0.25乘以进制取整数0，小数0.5乘以进制取整数1，且乘到1停止

0.125对应  0.001  即0*（1/2）+0*（1/4）+1*（1/8）=0.125，回看过程，1/q*b*b....每次取整数，最后等于1，相当于乘以

b的过程是对q约分，那么只要b包含q全部的因子即可。

#include <iostream>

#define ll long long
using namespace std;
ll gcd(ll a,ll b)
{
if(!b)return a;
return gcd(b,a%b); 
}
int main()
{
   cin.sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
int n; cin>>n;
while(n--)
{ 
 ll p,q,b;   cin>>p>>q>>b;
 ll g=gcd(p,q); p/=g; q/=g;//约分，将分母化成最简。 
if(p==0||q==1)//p==0 该数值为0显然任何形式都可以表示； q==1分母为1表示整数 ，都可以表示 
{
cout<<"Finite"<<endl; continue;
}
//若1/q可以被表示，则p/q也能被表示 
while(q!=1&&b!=1)
{
b=gcd(b,q);
q/=b; //约分 ，b必须含有q的全部因子才是有限小数 
} 
if(q==1)printf("Finite\n");
            else printf("Infinite\n");
} 


   return 0;
}