配点：$200$ 点

問題文

$P, Q$ は正の整数です．
整数 $K$ 未満の非負整数 $x$ であって次の条件を満たすものの個数を求めてください：

• $(x \bmod P) \bmod Q = (x \bmod Q) \bmod P$

制約

• $1 \leq \Phi \leq 10^5$
• $1 \leq P, Q < 2^{30}$
• $0 \leq K < 2^{60}$
• 入力はすべて整数

入力

各テストケースの入力は，それぞれ以下の形式で与えられる：

出力

答えを出力せよ．

サンプル

4
3 5 1
4 2 5
10 100 1000
1 1 0

1
5
1000
0