Rescue the Hackland
Practice
3.7 (104 votes)
Easy
Problem
82% Success 2895 Attempts 20 Points 1s Time Limit 256MB Memory 1024 KB Max Code

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 ≤ 106
1 ≤ K ≤ 103

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
118 votes
Tags:
AlgorithmsApprovedBinary SearchEasyOpenSorting
Points:30
1 votes
Tags:
Data StructuresGraph TheoryAlgorithmsApprovedMedium
Points:30
4 votes
Tags:
MathematicsMediumOpenApprovedNumber Theory