What is the expected number of nodes in a trie when 'N' words, each of length 'L' are inserted into it. The words are made up only of 0's and 1's. The words may be repeated and all possible permutations of words are equally likely. Initially the trie consists of only one node (root node).

Input

The first line of input contains an integer 't', denoting the number of test cases. Each of the next 't' lines contain 2 space separated integers 'N' and 'L'.

Output

For each test case, output one floating point value denoting the expected number of nodes in the trie. Output the values rounded off to 2 decimal places. Always print 2 digits after the decimal point.

To know more about tries visit here.

Example

Input:
2
1 3
2 2

Output:
4.00
4.25

Constraints:

t <= 25

1 <= N <= 300

1 <= L <= 300

Explanation:

Test case 1: There are 8 possible words of length 3. Which ever word is inserted into the trie, we get only 4 nodes.