시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 7 0 0 0.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


## 출처

• 문제의 오타를 찾은 사람: kdman98