A. Finite or not?time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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.OutputFor each question, in a separate line, print Finite if the fraction is finite and Infinite otherwise.ExamplesInput26 12 104 3 10OutputFiniteInfiniteInput41 1 29 36 24 12 33 5 4OutputFiniteFiniteFiniteInfiniteNote\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 
Input26 12 104 3 10
OutputFiniteInfinite
['implementation', 'math', '*1700']