Вам дано несколько запросов. Каждый запрос описывается тремя числами \(p\), \(q\) и \(b\). Необходимо ответить, является ли результат выражения \(p/q\) в системе счисления по основанию \(b\) конечной дробью.
Дробь в системе счисления по основанию \(b\) является конечной, если содержит конечное число цифр после запятой, в том числе дробь может и не содержать цифр после запятой.
В первой строке дано целое число \(n\) (\(1 \le n \le 10^5\)) — количество запросов.
Далее следуют \(n\) строк, описывающих запросы, по одному в строке. Каждый запрос — три целых числа \(p\), \(q\) и \(b\) (\(0 \le p \le 10^{18}\), \(1 \le q \le 10^{18}\), \(2 \le b \le 10^{18}\)). Все числа даны в системе счисления по основанию \(10\).
Для каждого запроса выведите в отдельной строке Finite, если дробь конечна, и Infinite — в противном случае.
\(\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\)
2 6 12 10 4 3 10
Finite Infinite
4 1 1 2 9 36 2 4 12 3 3 5 4
Finite Finite Finite Infinite
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач