EVERLAST - The fate of the pineapple

In order to help terraform Mars, astronauts have brought (among other things) N (0<=N<5) young, healthy pineapple plants.

This particular type of pineapple reproduces asexually in the following way:

  1. A single pineapple plant produces K (0<=K<15) new pineapple in one growing season.
  2. At the end of the growing season, the new pineapples are adults, and the old ones are dead.
  3. Increased levels of radiation have a P (0<=P<=1) chance of sterilizing any new pineapple that develops on Mars. This probability is independent for each pineapple.

What is the probability that the pineapple population will never die out?

Input

The first line is the number of test cases (no more than 10^5). Each of the following lines describes a test case. The integers N and K and the decimal number P are separated by single spaces.

Output

There will be one line for each test case. Each line will have the probability of eventual survival in percent, to two decimals, followed by the percent sign.

Example

Input:
5
1 3 0.6666666666666666
1 3 0.65
1 1 0
1 0 1
3 4 0.7101634622811129

Output:
0.00%
13.83%
100.00%
0.00%
70.94%

Added by:Paul Draper
Date:2009-05-05
Time limit:1s-3.255s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET

hide comments
2011-08-26 21:40:48 :D
First N pineapples are never sterilized by radiation.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.