You probably have played the game Throwing Balls into the Basket. It is a simple game. You have to throw a ball into a basket from a certain distance.

One day, we (the AIUB ACMMERs) were playing the game. But it was slightly different from the original game. In our version of the game, we were N people trying to throw balls into M identical Baskets. In each turn, we all were selecting a basket and trying to throw a ball into it. After the game, we saw exactly S balls were successful.

Now you will be given the value of N and M. For each player, the probability of throwing a ball into any basket successfully is P. Assume that there are infinitely many balls and the probability of choosing a basket by any player is 1/M. If multiple people choose a common basket and throw their ball, you can assume that their balls will not conflict, and the probability remains the same for scoring inside a basket. You have to find the expected number of balls entered into the baskets after K turns.

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing three integers N (1 ≤ N ≤ 16), M (1 ≤ M ≤ 100) and K (0 ≤ K ≤ 100) and a real number P (0 ≤ P ≤ 1). P contains at most three places after the decimal point.

For each case, print the case number and the expected number of balls. Errors less than 10^-6 will be ignored.