ストーリー

kazuppaくん、Awashくん、ゆ～さん、ルクくんはクリスマスパーティーの準備をしています。

ルクくんの担当は🎅サンタクロースです。

サンタクロースのルクくんは、🎄クリスマスが近づいてきたので、子どもたちに配るお菓子の準備をしていました。

そこで、ルクくんはより良いサンタクロースになるために、キャンディーの嬉しさを変えることができるとても素晴らしい機械を発明しました。

そこでルクくんは、ふとこのような疑問を抱きました。

ルク「できるだけ、いろんな嬉しさを子どもたちに配りたいな～」

ルク「持ってるキャンディーと作ったキャンディーからいくつか選んで、嬉しさを足し合わせた時に作ることのできない嬉しさの最大値は何だろう？」

ルクくんは考えた末、この疑問を形式化することにしました。

問題文

ルクくんは、子どもたちに配る🍭キャンディーをたくさん持っています。

それらのキャンディーは全て、価値が $1$ で嬉しさが $X$ です。

ルクくんは、嬉しさを変えることのできる強さ $d$ の機械を $N$ 種類開発しました。

種類 $i (1 \le i \le N)$ の機械は以下の操作を行うことができます。

• 価値が $i$ のキャンディーを入れると、キャンディーは以下のように変化する。
  • 価値が $i$ から $i+1$ に変化する。
  • 入れたキャンディーの嬉しさを $k$ としたとき、嬉しさが $k$ から $k+d$ に変化する。
• 価値が $i$ でないキャンディーを入れると何も起こらず、入れたキャンディーが戻って来る。

あなたは $Q$ 個のクエリが与えられるので以下の問題を解いてください。

$i$ 番目のクエリにおいて、ルクくんがたくさん持っている価値が $1$ で嬉しさが $X_i$ のキャンディーに対し、$N_i$ 種類の強さ $d_i$ の機械を好きな回数、好きな順序で用いることで生成できる任意のキャンディーをいくつでも( $0$ 個でも良い)選び、その嬉しさの総和として表すことができない最大の整数を求めなさい。

ただし、作ることのできない嬉しさの総和が $10^{1000}$ を超える選び方が存在する時、inf を出力してください。

入力

$Q$
$X_1\ N_1\ d_1$
$X_2\ N_2\ d_2$
$\vdots$
$X_Q\ N_Q\ d_Q$

制約

• $1 \le Q \le 2 \times 10^5$
• $1 \le X_i, N_i, d_i \le 10^9 (1 \le i \le Q)$

出力

各クエリへの答えを改行区切りで出力してください。

サンプル

3
2 2 5
2 1 2
1 1000000000 1

5
inf
-1