Ahmad was playing the famous game 2048, however, he found it very hard. He decided to create a simplified version of it on 1 dimension.
Basically, he has an array of length n that is initially empty.
He starts with a score of zero, then, the following steps are repeated until the array is full:
- A number appears in the right-most cell of the array. Either a 4 with probability
, or a 2 with probability 
. - All the cells are shifted once to the left by applying the following algorithm:
Go through the array from left to right, for each cell that contains a number, there are 3 options:
- if the cell to the left of it is empty, move it one step to the left.
- if the cell to the left of it has a number equal to the current number, add the sum of both numbers (twice the current number) to the score, empty the current cell, and multiply the number in the cell to the left of it by 2.
- if the cell to the left of it has a number not equal to the current number, do nothing.
for example, this array:
may become (with probability
) :
Soon, he realized that this game depends only on luck. To see how lucky he is, he asked you to find the expected score at the end of the game.
The first line of input contains one integer T, the number of test cases.
Each test case contains two integers n, the number of cells, and p, the probability that the new number is 4. (1 ≤ n ≤ 16) (0 ≤ p ≤ 100)
For each test case output one line containing the expected score.
Your answer will be considered correct if the relative error is less than 10 - 6.
3
1 50
2 25
3 20
0.000000
3.875000
15.725298
