Description

众所周知，智哥的数学是队伍里比较好的，这都得益于智哥对数论的学习，最近智哥看到了一道很有意思的数学题，当然这道题对智哥来说易如反掌，但是他还是想把这道题分享给亲爱的学弟们。

这道题是这样的，现在有一个序列 $A$, 序列的长度为$q$,序列每一位的定义为$A{i} = ((a+i×p) \% q)+1$ $(1≤i≤q)$。对于这个序列$A$，要求你求出一个最小的$k$，使得任意一个长度为$k$的$A$的子序列$B$，对于每个序列$B$都至少存在两个元素$B_i, B_j$ $(i≠j,1≤i,j≤k)$，$B_i$可以被$B_j$整除。

题目保证$p, q$互质。

$p$和$q$互质表示 $p$和$q$的最大公因数为1。 对于一个序列任意删除某几个(可能0个)元素得到的一个新序列就是这个序列的一个子序列。

$\%$为取模符号,$x\%y$即为$x/y$后余数,例如$6\%4=2$。

Input Format

题目包含多组样例。

在第一行输入一个正整数$T(1≤T≤10)$，表示样例个数。

对于每组样例在一行输入三个整数$a,p,q (0≤a≤10^9, 1≤p≤10^9, 2≤q≤10^6)$，分别对应题目中的变量。题目保证$p,q$互质。

Output Format

对于每组样例，在一行输出一个整数$k$，表示答案。

2
0 1 2
0 1 3

2
3