bee 2030 - Pit Stop

“Grazie, grazie, bellissimo!” – said a engineer of Scuderia Ferrari after an unexpected strategy which made then win the Formosa GP of 2016, famous street circuit of the Formula One calendar.

Formula One is a bit crazy sport. Sometimes, when the tyre is worn, it is worth to make a pit stop in order to put new tyres and do faster laps.

However, it is not always that making a pit stop translates into an advantage. It depends of the quantity of remaining laps and the pit stop time.

The tyres have a life span of few laps until being worn. Then, possibly a pit stop could be necessary in order to gain time with fresh tyres.

Are you capable of calculating the optimal strategy as a future Ferrari engineer?

Input

The input consists of a line containing a number N (1 ≤ N ≤ 1000) indicating the number of test cases. The following N lines represent a test case. Each test case is composed by five integers:

T₁, the lap time in milliseconds with a new tyre (1 ≤ T₁ ≤ 10⁶).
T₂, the lap time in milliseconds with a worn tyre (1 ≤ T₁ ≤ T₂ ≤ 10⁶).
A, the time of a pit stop in milliseconds (1 ≤ A ≤ 10⁶).
V, the number of laps until a new tyre becomes a worn tyre (1 ≤ V ≤ 100).
R, the number of laps of the Formosa GP (1 ≤ R ≤ 100).

Output

Each test case output must begin with the line “Teste #i”, indicating the test case number. After this, a new line should give the least time possible (sum of the time of each lap and pit stop) of the optimal strategy to complete the Formosa GP and the minimum number of pit stops possibles to minimize this time. These two information must be separated by a space.

After each test case, a blank line must be printed.

Input Sample	Output Sample
3 110000 113000 20000 15 70 110000 113000 20000 20 15 110000 112000 20000 15 70	Teste #1 7780000 4 Teste #2 1650000 0 Teste #3 7780000 3

Input Sample

Output Sample

3
110000 113000 20000 15 70
110000 113000 20000 20 15
110000 112000 20000 15 70

Teste #1
7780000 4

Teste #2
1650000 0

Teste #3
7780000 3