L. 抱歉，有钱是真的能为所欲为的

LiuRunky 喜欢玩媚宅抽卡手游，比如《后天方舟》、《碧绿航线》。

经过冷静分析，他发现很多抽卡游戏都遵循一个不成文的规矩，就是使用伪随机数。具体来说，每位玩家都会被分配一个质数模数 $P$ 和随机因子 $q$。该玩家第 $i$ 抽卡时，后台获得的随机数将是 $x_i = q^i\ mod\ P$($x\ mod\ P$ 即 $x$ 除 $P$ 后的余数)。由于游戏规定的出货率为 $2\%$（是不设保底的黑心游戏），所以程序员简单地将 $x_i$ 除 $50$ 的余数为 $0$ 的所有 $x_i$ 判定为出货。

既然是抽卡游戏，沉船总是不可避免的。但这对于精神亿万富豪的 LiuRunky 来说这根本不是问题。他总能从虚空中拿出足够的钱抽 $n$ 发，从根本上解决不出货的问题。不过在高强度抽完这么多发后，他已经精疲力竭，忘记了自己的总出货数量。请你帮助他统计一下。

第一行有一个正整数 $T(1\leq T\leq 20)$，表示数据组数。

对于每组数据，输入为 $3$ 个整数 $n(0\leq n\leq 1\times 10^{18})$，$P(50\leq P\leq 1\times 10^6)$，$q(2\leq q<P)$，含义均在题面中有所解释。

数据保证 $P$ 为质数。

对于每组数据，输出一个整数，表示出货数量。

样例输入

5
0 53 2
10 53 2
100 53 2
1000 53 2
1 1777 50

样例输出

0
0
2
19
1