問題文

貴方はある人とゲームをします。 貴方は $A$ 個のガムを、相手は $B$ 個のガムを持っています。 ただし持っているガムの個数は同じではないです。 持っているガムの内、それぞれに一個だけすっぱいガムが入っていて、それを食べてしまったら負けであり、それがどれなのかは互いに把握していません。 ゲームの先手は持っているガムの個数が多い方です。 自分のガムを持っている個数が相手のガムを持っている個数より $1$ 個だけ少なくなるように自分のガムからランダムに選び食べます。 この操作を勝負がつくまで続けます。 貴方の勝つ確率が与えられるので、 $1 \le A,B \le 10^8,A \neq B$ を満たす正整数の組 $A,B$ としてあり得るものの個数を求めてください。 ただし $1$ 回の入力で $S$ 個のテストケースが与えられます。

入力

$S$

$X$ $Y$

• 入力は全て整数である。
• $1 \le S \le 10^5$
• $1\le X < Y \le 10^7$
• $GCD(X,Y)=1$ であることが保証されます。

出力

最後に改行してください。

サンプル

1
1 4

25000000

1
1 8

12500000

3
17 100
123 500
6 25

1000000
200000
4000002