You are given several queries. Each query consists of three integers $\mathrm{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$

$\mathrm{(1\le n\le 105}$

) — the number of queries.

Next $n$

$\mathrm{lines\; contain\; queries,\; one\; per\; line.\; Each\; line\; contains\; three\; integers\; p,\; q,\; and\; b\; (0\le p\le 1018,\; 1\le q\le 1018,\; 2\le b\le 1018).\; 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

Note

$\frac{\mathrm{612=12=0,510}}{}$

$\frac{\mathrm{43=1,(3)10}}{}$

$\frac{\mathrm{936=14=0,012}}{}$

$\frac{\mathrm{412=13=0,13}}{}$

题意 ： 给两个数，以及一个所要求的进制，询问是否在此进制下，相除后是否为有限位小数

思路分析 ： 比赛的时候想了一个模拟，不过没有去写，旁边的大佬一直再和说，会超时，会超时，然后赛后才知道是用这样的，比如 10进制下，判断两数是否整除，只需要让除数已知除以 2 或者 5，当可以除到 1 的时候，代表是可以整除的，如果是换成任意进制下的一个数，则需要去除当前的数和 b进制的约数。

代码示例 ：

#define ll long longll gcd(ll a, ll b){    return b == 0?a:gcd(b, a%b);}int main() {    //freopen("in.txt", "r", stdin);    //freopen("out.txt", "w", stdout);    ll t;    ll p, q, b;        cin >> t;    while(t--){        scanf("%lld%lld%lld", &p, &q, &b);        ll g = gcd(p, q);        ll x = q / g;        ll f = gcd(b, x);                while(1){            if (f == 1) break;            while(x%f == 0) x /= f;            f = gcd(b, x);        }           if (x == 1) printf("Finite\n");        else printf("Infinite\n");    }    return 0;}