codeforces#P983A. Finite or not?

Finite or not?

Description

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/q in 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.

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

Next nn lines contain queries, one per line. Each line contains three integers pp, qq, and bb (0p10180 \le p \le 10^{18}, 1q10181 \le q \le 10^{18}, 2b10182 \le b \le 10^{18}). All numbers are given in notation with base 1010.

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

Input

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

Next nn lines contain queries, one per line. Each line contains three integers pp, qq, and bb (0p10180 \le p \le 10^{18}, 1q10181 \le q \le 10^{18}, 2b10182 \le b \le 10^{18}). 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.

Samples

输入数据 1

2
6 12 10
4 3 10

输出数据 1

Finite
Infinite

输入数据 2

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

输出数据 2

Finite
Finite
Finite
Infinite

Note

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

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

936=14=0,012\frac{9}{36} = \frac{1}{4} = 0,01_2

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