Expected Time for Tasting All Shops at a Food Festival

At a food festival, there are \(n\) shops initially (at time \(0\)), none of which have been tasted by Tian Yi. Starting from time \(1\), at each integer time step, Tian Yi chooses one of the \(n\) shops uniformly at random and tastes it. However, between every two consecutive time steps, each shop undergoes an independent withdrawal event with probability \(p\). When a shop withdraws, it is immediately replaced by a new shop (which has never appeared before), and the new shop is untasted.

Because a shop that has been tasted might later be replaced, its tasting is lost. The goal is to determine the expected time step at which (after the withdrawal events) all \(n\) shops present have been tasted by Tian Yi.

Note: The tasting happens first in a time step; then, independently, each shop (whether tasted or not) is replaced with probability \(p\), which resets its status to untasted. Thus, a fixed shop survives a time step with probability \(1-p\).

inputFormat

The first line contains an integer \(T\) (\(1 \le T \le 100\)) representing the number of test cases. Each test case consists of a single line containing an integer \(n\) (\(1 \le n \le 50\)) and a real number \(p\) (with \(0 \le p < 1\)), separated by a space.

outputFormat

For each test case, output a single line with the expected number of time steps until all \(n\) shops present are tasted, rounded to six decimal places.

sample

3
3 0.0
1 0.5
2 0.5

5.500000
2.000000
16.000000