Story

kazuppa-kun, Awash-kun, Yu~-san, and Luku-kun are preparing for a Christmas party.

Luku-kun is in charge of being 🎅Santa Claus.

With 🎄Christmas approaching, Santa Claus Luku-kun was preparing sweets to hand out to the children.

Then, in order to become a better Santa Claus, Luku-kun invented a truly wonderful machine that can change the happiness of a candy.

At that point, Luku-kun suddenly came up with the following question.

Luku: "I want to give the children as many different kinds of happiness as possible~"

Luku: "If I choose some candies from the ones I have and the ones I made, and add up their happiness, what is the maximum happiness that cannot be made?"

After some thought, Luku-kun decided to formalize this question.

Problem Statement

Luku-kun has many 🍭candies to hand out to the children.

All of these candies have value $1$ and happiness $X$.

Luku-kun has developed $N$ types of machines of strength $d$ that can change happiness.

A machine of type $i (1 \le i \le N)$ can perform the following operation.

• When a candy of value $i$ is put in, the candy changes as follows.
  • Its value changes from $i$ to $i+1$.
  • Letting $k$ be the happiness of the candy put in, its happiness changes from $k$ to $k+d$.
• When a candy whose value is not $i$ is put in, nothing happens and the candy put in is returned.

You are given $Q$ queries, so solve the following problem.

In the $i$-th query, starting from Luku-kun's many candies of value $1$ and happiness $X_i$, use the $N_i$ types of machines of strength $d_i$ any number of times and in any order. Choose any number ($0$ is allowed) of arbitrary candies that can be produced this way, and find the maximum integer that cannot be represented as the sum of their happiness.

However, if there is a way of choosing such that the sum of happiness that cannot be made exceeds $10^{1000}$, output inf.

Input

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

Constraints

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

Output

Output the answer to each query, separated by newlines.

Sample

3
2 2 5
2 1 2
1 1000000000 1

5
inf
-1