C. Sisyphus's Labor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have probably heard the legend of Sisyphus — as punishment for various offenses against the gods, he is forced to push a heavy stone up a mountain.

But when the stone reaches the top — it immediately rolls back down, and Sisyphus is forced to start all over again.

This has been going on for more than one century already — and Hades (the ruler of the underworld) decided to somehow make this action more interesting.

Now Sisyphus is forced to drag the stone along an infinite straight line.

During the day, Sisyphus can drag the stone by at most $$$A$$$ meters to the right (in the positive direction).

But at night, a strong wind starts blowing, which blows Sisyphus together with the stone to the left (in the negative direction).

To make things more interesting, the wind gets stronger every night — on the $$$i$$$-th night, the wind will blow Sisyphus $$$i \cdot B$$$ meters to the left.

Hades is interested in watching Sisyphus as long as he makes at least some progress to the right. Otherwise, Hades changes the parameters $$$A$$$ and $$$B$$$ and starts Sisyphus's punishment from the beginning.

For each pair $$$A$$$ and $$$B$$$, determine the maximum distance to the right Sisyphus can advance.

Input

The first line contains an integer $$$Q$$$ $$$(1 \le Q \le 10^4)$$$ — the number of different punishment variants.

Each of the next $$$Q$$$ lines contains two integers $$$A_i$$$ and $$$B_i$$$ $$$(1 \le A_i, B_i \le 10^9)$$$ separated by a space — the distance Sisyphus can drag the stone to the right in one day, and the initial wind strength for the $$$i$$$-th punishment variant.

Output

Print $$$Q$$$ lines.

In the $$$i$$$-th line, print one integer $$$D_i$$$ — the maximum positive distance Sisyphus can advance in the $$$i$$$-th punishment.

Example
Input
5
10 3
3 10
42 42
12345 876
987654321 1
Output
22
3
42
93195
487730529388812681
Note

The first punishment.

Let us consider Sisyphus's coordinate on the line after each day and night:

  • at the beginning, he is at $$$0$$$;
  • after the first day, he moved to $$$10$$$ meters to the right;
  • after the first night, he was blown $$$3$$$ meters to the left — that is, he ended up at $$$7$$$;
  • after the second day, he advanced to $$$17$$$;
  • after the second night, he was blown $$$2 \cdot 3$$$ meters to the left — now he is at $$$11$$$;
  • after the third day, he dragged the stone to $$$21$$$;
  • after the third night, the wind pulled him $$$3 \cdot 3$$$ meters — and Sisyphus ended up at $$$12$$$;
  • after the fourth day, Sisyphus reached $$$22$$$;
  • after the fourth night, the wind moved Sisyphus by $$$4 \cdot 3$$$ meters — to $$$10$$$;
  • after the fifth day, Sisyphus managed to reach $$$20$$$;
  • after the fifth night, Sisyphus was blown $$$5 \cdot 3$$$ meters — to $$$5$$$.

It can be seen that Sisyphus advanced maximally to $$$22$$$ — after that, the wind will keep pushing him further and further to the left.

The second punishment.

  • during the day, Sisyphus moved $$$3$$$ meters to the right;
  • during the night, Sisyphus was pulled $$$10$$$ meters to the left — to coordinate $$$-7$$$.

Hades realized that he had overcomplicated things — and ended this trial.

The third punishment.

  • on the first day, Sisyphus moved as much as $$$42$$$ meters;
  • on the first night, the wind pulled Sisyphus back to $$$0$$$;
  • on the second day, Sisyphus again reached $$$42$$$ meters;
  • on the second night, the wind had already pulled Sisyphus by $$$2 \cdot 42$$$ meters — to the mark $$$-42$$$.

It was pointless to continue any further.

The fourth punishment.

This example is intended for additional verification of the correctness of your calculations.

The fifth punishment.

This example is intended for additional verification of the efficiency of your calculations.