{"raw_statement":[{"iden":"statement","content":"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.\n\nA 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."},{"iden":"input","content":"The first line contains a single integer $n$ ($1 \\le n \\le 10^5$) — the number of queries.\n\nNext $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$."},{"iden":"output","content":"For each question, in a separate line, print _Finite_ if the fraction is finite and _Infinite_ otherwise."},{"iden":"examples","content":"Input\n\n2\n6 12 10\n4 3 10\n\nOutput\n\nFinite\nInfinite\n\nInput\n\n4\n1 1 2\n9 36 2\n4 12 3\n3 5 4\n\nOutput\n\nFinite\nFinite\nFinite\nInfinite"},{"iden":"note","content":"$\\frac{6}{12} = \\frac{1}{2} = 0,5_{10}$\n\n$\\frac{4}{3} = 1,(3)_{10}$\n\n$\\frac{9}{36} = \\frac{1}{4} = 0,01_2$\n\n$\\frac{4}{12} = \\frac{1}{3} = 0,1_3$"}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"你被给予若干查询。每个查询包含三个整数 $p$、$q$ 和 $b$。你需要判断 $p \\\\/ q$ 在以 $b$ 为基的表示中是否为有限小数。\\n\\n在以 $b$ 为基的表示中，一个分数是有限的，当且仅当它的小数点后包含有限位数字。也可能小数点后数字个数为零。\\n\\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 查询的个数。\\n\\n接下来 $n$ 行，每行包含一个查询，包含三个整数 $p$、$q$ 和 $b$ ($0 lt.eq p lt.eq 10^(18)$，$1 lt.eq q lt.eq 10^(18)$，$2 lt.eq b lt.eq 10^(18)$)。所有数字均以十进制给出。\\n\\n对于每个查询，在单独一行中，若分数是有限的则输出 _Finite_，否则输出 _Infinite_。\\n\\n$frac(6, 12) = frac(1, 2) = 0, 5_(10)$\\n\\n$frac(4, 3) = 1, (3)_(10)$\\n\\n$frac(9, 36) = frac(1, 4) = 0, 01_2$\\n\\n$frac(4, 12) = frac(1, 3) = 0, 1_3$ \\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 查询的个数。接下来 $n$ 行，每行包含一个查询，包含三个整数 $p$、$q$ 和 $b$ ($0 lt.eq p lt.eq 10^(18)$，$1 lt.eq q lt.eq 10^(18)$，$2 lt.eq b lt.eq 10^(18)$)。所有数字均以十进制给出。\"},{\"iden\":\"output\",\"content\":\"对于每个查询，在单独一行中，若分数是有限的则输出 _Finite_，否则输出 _Infinite_。\"},{\"iden\":\"examples\",\"content\":\"输入26 12 104 3 10输出FiniteInfinite输入41 1 29 36 24 12 33 5 4输出FiniteFiniteFiniteInfinite\"},{\"iden\":\"note\",\"content\":\"$frac(6, 12) = frac(1, 2) = 0, 5_(10)$\\n$frac(4, 3) = 1, (3)_(10)$\\n$frac(9, 36) = frac(1, 4) = 0, 01_2$\\n$frac(4, 12) = frac(1, 3) = 0, 1_3$ \"}]}","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of queries.  \nFor each query $ k \\in \\{1, \\dots, n\\} $, let $ (p_k, q_k, b_k) \\in \\mathbb{Z}^3 $ be the input triple, where:  \n- $ 0 \\leq p_k \\leq 10^{18} $,  \n- $ 1 \\leq q_k \\leq 10^{18} $,  \n- $ 2 \\leq b_k \\leq 10^{18} $.  \n\nLet $ r_k = \\frac{p_k}{q_k} $, and define $ \\tilde{r}_k = \\frac{p_k / \\gcd(p_k, q_k)}{q_k / \\gcd(p_k, q_k)} = \\frac{p_k'}{q_k'} $ as the reduced form of the fraction.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. For all $ k \\in \\{1, \\dots, n\\} $:  \n   - $ 0 \\leq p_k \\leq 10^{18} $  \n   - $ 1 \\leq q_k \\leq 10^{18} $  \n   - $ 2 \\leq b_k \\leq 10^{18} $\n\n**Objective**  \nFor each query $ k $, determine whether the fractional part of $ \\tilde{r}_k = \\frac{p_k'}{q_k'} $ has a finite representation in base $ b_k $.  \n\nThis occurs **if and only if** all prime factors of $ q_k' $ are also prime factors of $ b_k $.  \n\nEquivalently:  \nLet $ d_k = \\gcd(p_k, q_k) $, and $ q_k' = \\frac{q_k}{d_k} $.  \nLet $ g_k = \\gcd(q_k', b_k) $.  \nWhile $ g_k > 1 $, replace $ q_k' $ by $ \\frac{q_k'}{g_k} $ and $ g_k $ by $ \\gcd(q_k', b_k) $.  \nThen, $ \\frac{p_k}{q_k} $ has a finite representation in base $ b_k $ **if and only if** $ q_k' = 1 $ after this process.  \n\n**Output**  \nFor each $ k $, output:  \n- “Finite” if $ q_k' = 1 $ after removing all common factors with $ b_k $,  \n- “Infinite” otherwise.","simple_statement":null,"has_page_source":false}