Hackland is being attacked by Greyland, and you have been assigned the job to save it. Your enemies, known as Grey hats, are numbered starting from L to R, both inclusive. But, here is the fun part: Grey hats are known to switch sides, and you need to make full use of it to get some of them on your side.

Now, two Grey hats are said to be dangerous if they form a volatile pair. A volatile grey hat pair is one where i<=j * K and j<=i * K, where 'i' and 'j' are the numbers of Grey hats (i != j). So, basically you can't afford a dangerous grey hat pair in your army.

Now given L,R and K, find the maximum number of Grey hats you can get to your side, such that no two of them form a volatile pair.

Input Format:
First line contains T, the number of test cases. T lines follow.
Each line consists of 3 space seperated number denoting L, R and K.

Output Format:
For each test case, print the answer, the maximum number of Grey hats you can get to your side.

Constraints:
1 ≤ T ≤ 200
1 ≤ L ≤ R ≤ 10⁶
1 ≤ K ≤ 10³