Problem Statement:

Now it is time for your math homework. A Tornado operation T(n) is defined as follows:

a is a given constant, and + is the set of positive integers. X

_{n} and Y

_{n} are positive integers chosen such that X

_{n} ≤ X

_{n+1} and Y

_{n} ≤ Y

_{n+1}, for all positive n. Also, minX ≤ X

_{n} ≤ maxX and minY ≤ Y

_{n} ≤ maxY, for all positive n.

For example if a = 1, X

_{1} = 2, X

_{2} = 4, and Y

_{1} = Y

_{2} = 3, then:

Given a, minX, maxX, minY, maxY and two positive integers P and C, your homework is to find the minimum value of n such that T(n) + C is divisible by 10P, by choosing appropriate values for X

_{1},..., X

_{n} and Y

_{1},..., Y

_{n}.

Input Format:

Your program will be tested on one or more test cases. The first line of the input will contain a single integer T, the number of test cases (1 ≤ T ≤ 200). Next T lines contain the test cases, each on a single line.

Each of those lines will contain 7 integers, a, minX, maxX, minY, maxY, P and C, separated by single spaces, given in this order (1 ≤ minX, maxX, minY, maxY ≤ 100, 1 ≤ P ≤ 3, 1 ≤ a, C ≤ 1,000,000).

Output Format:

For each test case, output, on a single line, a single integer representing the minimum value for n such that T(n) + C is divisible by 10^{P}. If there is no such value, output '-1' instead.

Sample Input:

4
4 1 1 1 2 1 5
4 1 100 1 100 1 6
3 1 1 2 2 2 11
1 2 2 1 1 3 2

Sample Output:

1
0
2
-1