시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB7000.000%

문제

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

\[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.

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.

예제 입력 1

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

1
0
2
-1