G. Gatuno's Descent into Psychopathy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The once-kind feline Gatuno is a very good and heart-guided person. As every good person, his goodness can be measured. He carries a heart of size $$$H_1$$$. Unfortunately, now he seeks to shed his humanity. His twisted goal: reduce his heart to size $$$H_2$$$ or smaller through a horrifying ritual — biting innocent dogs.

Each bite comes at a terrible cost to his remaining conscience, but makes subsequent bites easier in his dark transformation...

After biting $$$n$$$ dogs, the rule of shrinking heart is:

- His heart shrinks: $$$ H_{n} = H_1 \times \left(\frac{B-1}{B}\right)^n $$$ Therefore, each subsequent bite requires $$$ \frac{1}{B} $$$ of the previous emotional pain.

Help Gatuno to find the minimum minimum number of dogs Gatuno must bite to reduce his heart size to $$$H_2$$$ or smaller.

Input

The input consists of multiple test cases.

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$).

Each of the next $$$T$$$ lines describes one test case with three space-separated integers:

- $$$H_1$$$: Initial heart size ($$$1 \lt H_1 \leq 10^{12}$$$) — Yes, Gatuno was a really good feline - $$$H_2$$$: Target heart size ($$$0 \lt H_2 \lt H_1$$$) - $$$B$$$: Brutality factor ($$$2 \leq B \leq 2 \times 10^5$$$)

Output

For each test case, output a single integer — the minimum number of dogs Gatuno must bite to reduce his heart size to $$$H_2$$$ or smaller.

Example
Input
3
100 50 2
1000 1 10
1000 100 10
Output
1
66
22