Tornado operation homework

Time for your math homework. A Tornado operation $T(n)$ is defined as follows.

$T(n) = \begin{cases} a & (n = 0) \\ \left[ T(n-1) + X_n \right]^{Y_n} & (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 so that $X_n \le X_{n+1}$ and $Y_n \le Y_{n+1}$ hold for every positive $n$. They also satisfy $\min X \le X_n \le \max X$ and $\min Y \le Y_n \le \max Y$ for every 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$

You are given $a$, $\min X$, $\max X$, $\min Y$, $\max Y$ and two positive integers $P$ and $C$. Your homework is to find the smallest $n$ for which $X_1, \ldots, X_n$ and $Y_1, \ldots, Y_n$ can be chosen so that $T(n) + C$ is divisible by $10^P$. Here $n$ is a non-negative integer, and $n = 0$ means that no operation is applied at all, so the value is $T(0) = a$.

The input holds one or more test cases. The first line contains a single integer $T$, the number of test cases ($1 \le T \le 200$). Each of the next $T$ lines holds one test case.

Each of those lines contains 7 integers $a$, $\min X$, $\max X$, $\min Y$, $\max Y$, $P$ and $C$ in this order, separated by single spaces ($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$).

For each test case, print on a single line the smallest $n$ such that $T(n) + C$ is divisible by $10^P$. If no such $n$ exists, print -1 instead.