The young computer scientist began researching how the sum of the digits of positive integers changes when multiplying and dividing by different one-digit numbers. Once he was asked if it was possible to find the number A again, given the sum of its digits and the sum of the digits of the number D×A, where D — is a single-digit number. given number. Quite quickly, he replied that it was not enough to find the number А of this information. For example, the numbers 9 and 45 have the same sum of digits. If you multiply them by 5, you will get the numbers 45 and 225, which are numbers with the same sum of digits.

At that time, the young computer scientist decided to find the answer to the above question under the condition that he knew the number K — where K is the number of digits in the number A. Unfortunately, he was disappointed. Some numbers have the same sum of digits, the same number of digits, and after multiplying by the same one-digit number, they still get results with the same sum of digits. Example 42 and 51 with D = 3.

Continuing, our young computer scientist posed the following problem: find the smallest positive integer A with K digits in the decimal base system, whose sum of digits is equal to S, and the number D×A has sum of digits equals P.

Write a program to solve this problem.

Input:

Each test contains multiple test cases.

• The first line contains a single integer t (1 ≤ t ≤ ~10^3~) — the number of test cases. Each test case consists of two lines.
• The next t lines, each line contains 4 positive integers K, S, P, D separated by at least one space (1 ≤ K ≤ 10, 1 ≤ S ≤ 9K, 1 ≤ P ≤ 9(K+1)), 1 ≤ D ≤ 9).

Output:

For each test case, prints an integer that is the number A if found. Otherwise, if not found, print -1.

Example

Input

2
2 9 9 5
2 8 10 3

Output

18
-1