A. Minecraft Dragon
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are fighting the final dragon boss in Minecraft. The dragon has health points $$$n$$$, and you have a sword with the following properties:

  • In the $$$i$$$-th attack, if $$$i$$$ is a multiple of $$$3$$$, deal $$$2$$$ points of damage; otherwise, deal $$$1$$$ point of damage.

Your initial health point is $$$m$$$ initially. Every time after you hit the dragon, if the health points of the dragon are less than $$$1$$$, it is defeated. Otherwise, it immediately rebounds $$$k$$$ $$$(k \lt m)$$$ points of damage to you. If your health point is less than $$$1$$$, you are defeated and cannot take any action.

In addition, you can use bandages any number of times. When you use a bandage, it restores your health to $$$m$$$. Note that using a bandage and attacking are independent.

Find the minimum number of bandages required to defeat the dragon.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t\le 100$$$), the number of test cases.

The only line of each test case contains three integers $$$n,m,k$$$ ($$$1\le n,k\le 100$$$, $$$k \lt m \le 101$$$).

Output

For each test case, output the minimum number of bandages required to defeat the dragon.

Example
Input
4
4 3 2
4 3 1
10 7 3
96 101 23
Output
1
0
3
17
Note

In the first test case, the optimal action is:

  • Attack.
  • Use a bandage.
  • Attack.
  • Attack.

After that, the dragon is defeated. The number of bandages used is $$$1$$$.