Challenge 24 Electronic Contest Practice

A craftsman and his apprentices are producing samurai swords. However at the end of its production each sword is tested and breaks with a probability p, independently of everything else.

The craftsman has an order of N swords which he has to produce in the next K months. At the end of that period, if he has not managed to produce K swords which passed the test, he has to pay a penalty of A gold coins for each sword missing. Surplus swords and swords that failed the test are not worth anything.

At the beginning of each month, the craftsman has to decide the number of swords they try to produce that month. Producing at least one sword has a fixed cost of C units plus an additional 1 unit per sword (regardless whether the sword passes the test or not).

Calculate the expected cost of the whole production if the craftsman follows an optimal plan to minimize the expected cost.

Input

The input files contain several test cases. The first line of the file contains a single integer, the number of test cases, T. The next T lines each describe a test case.

The test cases are described in lines containing the numbers p, N, K, A and C separated by spaces.

Output

Output a single integer (the expected cost rounded down) for every test case on a separate line.

This is the electronic variant of the problem. Read more here about submitting solutions!

Example

Input
2
0.1 1 1 5 1
0.9 1 1 5 1
Output
2
5

(In the first case, the expected value is 2.5 before rounding, in the second case it is 5.)