Sequence

Problem Description

Input

The first line has only one integer $T$, indicates the number of tasks.

Then, for the next $T$ lines, each line consists of $6$ integers, $A$ , $B$, $C$, $D$, $P$, $n$. $1 \leq T \leq 20 \\ 0 \leq A, B, C, D \leq 10^9 \\ 1 \leq P, n \leq 10^9$

Sample Input

2

3 3 2 1 3 5

3 2 2 2 1 4

Sample Output

36
24

Source

2018 Multi-University Training Contest 7