A witch has imprisoned Bob in the 1st room of the Central Witchland Hotel. The hotel is weird. All the rooms are numbered linearly, i.e. 1, 2, 3,….., n, n + 1, … and so on. Those rooms have no doors or windows except the rooms which have a room number greater than n. From the rooms having a room number greater than n, Bob can get out of the hotel. That means Bob has no way to get out of the hotel without reaching a room which has doors or windows.
Luckily, Bob has found a device that generates a number M from 0 to K – 1 with equal probability and it will teleport Bob to the Mth room from the current room. This means if Bob is currently in Xth room and the device generates M, then he will be teleported to the (X + M)th room. You have to determine what is the expected number of times he has to use that device to get out of the hotel.
Input
The first line of the input will contain an integer, T, number of test cases to follow. Each of the next T lines will continue two integer numbers, n and k, as discussed before.
1 ≤ T ≤ 105
1 ≤ n ≤ 106
2 ≤ K ≤ 10
Output
Print T lines, answer to each test case. Your solution will be considered correct if the absolute difference between your answer and the judge's answer is less than 10-6.
Sample
| Input | Output |
|---|---|
1 1 3 | 1.50000000 |
You have to go to any room numbered greater than n, not in n.
If that device generates 0, he'll stay in the same room.
