토네이도 연산 숙제

수학 숙제를 할 시간이다. 토네이도 연산 $T(n)$은 다음과 같이 정의한다.

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

$a$는 주어지는 상수이고, $\mathbb{Z}^{+}$는 양의 정수의 집합이다. $X_n$과 $Y_n$은 양의 정수이며, 모든 양의 정수 $n$에 대해 $X_n \le X_{n+1}$과 $Y_n \le Y_{n+1}$을 만족하도록 고른다. 또 모든 양의 정수 $n$에 대해 $\min X \le X_n \le \max X$이고 $\min Y \le Y_n \le \max Y$이다.

예를 들어 $a = 1$, $X_1 = 2$, $X_2 = 4$, $Y_1 = Y_2 = 3$이면 다음과 같다.

$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$

$a$, $\min X$, $\max X$, $\min Y$, $\max Y$와 두 양의 정수 $P$, $C$가 주어진다. $X_1, \ldots, X_n$과 $Y_1, \ldots, Y_n$을 적절히 골라 $T(n) + C$가 $10^P$로 나누어떨어지게 만들 때, $n$의 최솟값을 구하는 것이 숙제다. $n$은 0 이상의 정수이며, $n = 0$은 연산을 한 번도 적용하지 않고 $T(0) = a$를 그대로 쓴다는 뜻이다.

입력은 테스트 케이스 여러 개로 이루어진다. 첫 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 200$). 이어지는 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다.

각 줄에는 정수 7개 $a$, $\min X$, $\max X$, $\min Y$, $\max Y$, $P$, $C$가 이 순서대로 공백 하나로 구분되어 주어진다 ($1 \le \min X, \max X, \min Y, \max Y \le 100$, $1 \le P \le 3$, $1 \le a, C \le 1\,000\,000$).

각 테스트 케이스마다 $T(n) + C$가 $10^P$로 나누어떨어지는 $n$의 최솟값을 한 줄에 하나씩 출력한다. 그런 $n$이 없으면 대신 -1을 출력한다.