31. Homework

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

a is a given constant, and + is the set of positive integers. Xn and Yn are positive integers chosen such that Xn ≤ Xn+1 and Yn ≤ Yn+1, for all positive n. Also, minX ≤ Xn ≤ maxX and minY ≤ Yn ≤ maxY, for all positive n.

For example if a = 1, X1 = 2, X2 = 4, and Y1 = Y2 = 3, then:

Given a, minX, maxX, minY, maxY 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 10P, by choosing appropriate values for X1,..., Xn and Y1,..., Yn.

Input Format:
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, minX, maxX, minY, maxY, P and C, separated by single spaces, given in this order (1 ≤ minX, maxX, minY, maxY ≤ 100, 1 ≤ P ≤ 3, 1 ≤ a, C ≤ 1,000,000).

Output Format:
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 10P. If there is no such value, output '-1' instead.

Sample Input:
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

Sample Output:
1 0 2 -1

 Added by: abdelkarim Added at: 2014-02-26 01:15:00 UTC Time Limit: 5 seconds Partial score: No Source: ACM Arab Collegiate Programming Contest 2011