思路

• 关键结论：将分数约分为 $p'/q'$，其中 $q' = q / \gcd(p,q)$。分数在 $k$ 进制下为有限小数，当且仅当 $q'$ 的所有质因子都来自 $k$。等价地，存在某个正整数 $t$ 使

• 等价算法：反复用 $\gcd(q', k)$ 去除 $q'$ 中与 $k$ 的公共质因子，直到 $\gcd(q', k) = 1$。若最终得到 $q' = 1$，则为有限小数，否则不是。
• 步骤：

题目内容

小美是一位数学爱好者，她想知道给定的有理数 $\frac{p}{q}$ 在 $k$ 进制下是否为一个有限小数。

换句话说，她希望判断在基数为 $k$ 的表示中，该分数的小数部分是否会在有限位后结束，而不是无限循环。

例如，$\frac{1}{2}$ 在十进制下装示为 $0.5$ ，是有限小数；相比之下，$\frac{1}{3}$ 在十进制下表示为 $0.3$ ，不是有限小数。

输入描述

第一行输入一个整数 $T(1≤T≤10^5)$ ，表示测试数据的组数。

接下来 $T$ 行，每行输入三个整数 $p,q,k(1≤p,q≤10^{18},2≤k≤10^{18})$，分别表示分子 $p$、分母 $q$ 和进制基数。

输出描述

对于每一组测试数据，输出一行结果，若 $\frac{p}{q}$ 在 $k$ 进制下是 有限小数，则输出 $yes$ ；否则输出 $no$ 。

样例1

输入

3
1 2 10
1 3 10
5 4 2

输出

yes
no
yes

说明

• $\frac{1}{2}$在十进制下为 $0.5$ ，是有限小数，因此输出 $yes$ ；

• $\frac{1}{3}$在十进制下为 $0.3$，是无限循环小数，因此输出 $no$；

• $\frac{3}{4}$在二进制下为 $0.11_2$，是有限小数，因此输出 $yes$ 。