G - Mod P <-> Mod Q

配点： 点

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

• 入力はすべて整数

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

答えを出力せよ．

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

1
5
1000
0