# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Expected Result

A witch has imprisoned Bob in the **1 ^{st}** room of the Central Witchland Hotel. The hotel is weird. All the rooms are numbered linearly, i.e.

*. Those rooms have no doors or windows except the rooms which have a room number*

**1, 2, 3,….., n, n + 1, … and so on****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

**M**room from the

^{th}**current**room. This means if Bob is currently in

**X**room and the device generates

^{th}**M**, then he will be teleported to the

**(X + M)**room. You have to determine what is the

^{th}**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** ≤ 10^{5}

1 ≤ **n** ≤ 10^{6}

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.42% Solution Ratio

tanimahossainEarliest,

solaimanopeFastest, 0.1s

solaimanopeLightest, 1.7 MB

Shaad221BShortest, 755B

Login to submit