The N-th Element

A[0 ~ N-1] and B[0 ~ N-1] are two strictly increasing arrays of N integers each; that is, A[i] < A[j] if i < j and B[i] < B[j] if i < j, where 0 ≤ i, j ≤ N-1.

Definition of array A: A[i] = p*i2 + q*i + r (where p, q, r are positive coefficients)

Definition of array B: B[i] = x*i2 + y*i + z (where x, y, z are positive coefficients)

You can assume that all of the numbers can be stored in long long int (64 bits). Your task is to "efficiently" find the N-th smallest element among these two arrays of N integers each (thus a total of 2*N integers).

For example, suppose p=2, q=2, r=2, and x=1, y=2, z=3, that is, A[i] = 2*i2 + 2*i + 2 and B[i] = 1*i2 + 2*i + 3

Then given N=3: A[0~2] = {2, 6, 14} and B[0~2] = {3, 6, 11}

Among these two strictly increasing (sorted) arrays, {2, 6, 14} and {3, 6, 11}, the N-th (3rd) smallest element is 6.

Input

The first line contains an integer, M (1 ≤ M ≤ 100), which indicates the number of test cases in the following. Each test case contains three lines: the first line contains three positive integers, p, q, r (i.e., coefficients of array A, separated by space), the second line contains three positive integers, x, y, z (i.e., coefficients of array B, separated by space), and the third line contains an integer, N (1 ≤ N ≤ 10^7), which is the size of arrays A and B.

Output

For each test case, print the N-th smallest element among the two arrays (consisting of a total of 2*N elements).

5
1 2 3
2 2 2
3
1 2 3
2 2 2
4
1 2 3
2 2 2
5
4 3 10
5 6 5
10
2 1 7
10 6 5
10

6
6
11
109
85