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

[T(n) =  \begin{cases} a & \text{where } n = 0, \ \left[ T(n - 1) + X_n \right]^{Y_n} & \forall  n \in \mathbb{Z}^{+} \end{cases}]

(a) is a given constant, and (\mathbb{Z}^{+}) is the set of positive integers. (X_n) and (Y_n) are positive integers chosen such that (X_n \le X_{n+1}) and (Y_n \le Y_{n+1}), for all positive (n). Also, (\min{X} \le X_n \le \max{X}) and (\min{Y} \le Y_n \le \max{Y}), for all positive (n).

For example if (a = 1), (X_1 = 2), (X_2 = 4), and (Y_1 = Y_2 = 3), then:

(T(2) = \left[T(1) + X_2 \right] ^{Y_2} = \left[(T(0) + X_1)^{Y_1} + X_2 \right]^{Y_2} = \left[ (1+2)^3 + 4 \right] ^ {3} = 29791)

Given (a), (\min{X}), (\max{X}), (\min{Y}), (\max{Y}) 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 (10^P), by choosing appropriate values for (X_1), ..., (X_n) and (Y_1), ..., (Y_n).

입력 형식

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.</p>

Each of those lines will contain 7 integers, (a), (\min{X}), (\max{X}), (\min{Y}), (\max{Y}) , (P) and (C), separated by single spaces, given in this order (1 ≤ (\min{X}), (\max{X}), (\min{Y}), (\max{Y}) ≤ 100, 1 ≤ (P) ≤ 3, 1 ≤ (a), (C) ≤ 1, 000, 000).

출력 형식

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.

예제 입력

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

예제 출력

1
0
2
-1