Input : b.in

Output : standard output

Consider the following recurrence relation defined on nonnegative integral values of n:

Here a and b are constants such that the following two conditions are satisfied:

Given the values of , , , and , your job is to write a program that calculates the value of . You may safely assume that will be an integer with absolute value not exceeding .

The first line of the input file contains an integer N (1 £ N £ 10,000) denoting the number of test cases to follow.

Each of the following N lines contains five (5) values in the following order: , , , and . Here, and are integers with absolute values not exceeding , and is a nonnegative integer not greater than . On the other hand, and are floating-point numbers satisfying the two conditions stated in the problem description. Be assured that .

For each test case in the input file print a separate line containing the value of .

3
0 1 1 1 20
0 1 -1 0 1000000000
-1 1 4 -3 18

6765
-1
387420487