問題文

アリスは無限に広がる二次元平面上の街に住んでいます。アリスの自宅は原点、すなわち座標 $(x, y) = (0, 0)$ にあります。

この街には、任意の非負整数 $n$ について直線 $x = An$ 、任意の非負整数 $m$ について直線 $y = Bm$ で表される道路が敷かれています。これ以外に道路はありません。

アリスはこの街の $1$ 点 $(x, y)$ を選んでカフェを建てたいと考えています。カフェを建てる場所の候補地 $(x, y)$ は、以下の条件がすべて満たされている必要があります。

• $x$ と $y$ はともに正の整数である。
• 自宅 $(0, 0)$ からのマンハッタン距離が $N$ 以下である。すなわち、 $x + y \leq N$ を満たす。
• 自宅 $(0, 0)$ から道路の上のみを通って $(x, y)$ にたどり着ける。

カフェを建てる場所の候補地 $(x, y)$ として考えられる点はいくつありますか？

テストケースが $T$ 個与えられるので、それぞれについて解いてください。

入力

入力は標準入力から与えられる。 $1$ 行目は以下の形式で与えられる。

$T$

以下、 $T$ 個のテストケースがそれぞれ以下の形式で与えられる。

$N$ $A$ $B$

出力

$T$ 行にわたって出力せよ。$i$ $(1 \leq i \leq T)$ 行目には、 $i$ 番目のテストケースに対する答えを出力せよ。

この問題の制約下で、答えは $2^{63}$ 未満であることが証明できる。

最後に改行すること。

サンプル

サンプル1

入力

5
10 2 3
8 9 10
1200 1 2
31415 92 65
123456789 12345 67890

出力

27
0
719400
12841651
729437374182

$5$ つのテストケースが与えられています。

$1$ つめのテストケースでは、下図のように直線 $x = 0, x = 2, x = 4, x = 6, \dots$ と、 $y = 0, y = 3, y = 6, y = 9, \dots$ で表される道路が敷かれています。

例えば、 $(2, 2)$ や $(6, 3)$ 、 $(1, 9)$ は、自宅からのマンハッタン距離が $10$ 以下であり、かつ上図のような経路で道路上を通ってたどり着くことができるので、カフェを建てるための条件を満たします。条件を満たす座標は他にもあり、候補地は全部で $27$ 個です。

$2$ つめのテストケースでは、カフェを建てられる座標は存在しません。 $0$ を出力してください。カフェを建てる座標は $x, y$ ともに正であることに注意してください。

答えが32bit 整数に収まらない場合があります。注意してください。