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