H. Palindrome Number
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A palindrome number is a number that can be read the same way from left to right and from right to left. For example: 961169, 111, 554455 are palindromes, while 856, 10180, 7226 are not.

Find the largest palindrome number that satisfies the following rules:

  • The number of its digits is equal to n, and must not contain leading zeros.
  • The sum of its digits is equal to s.

If there is no such number print  - 1.

Input

The first line of the input contains an integer T (1 ≤ T ≤ 500), where T is the number of the test cases.

Each test case has one line that contains two integers n (1 ≤ n ≤ 106) number of digits, and s (1 ≤ s ≤ 9 × 106) sum of digits.

Output

For each test case, print a single integer that represents the largest palindrome number that satisfies the mentioned rules, if there is no such number print  - 1.

Example
Input
2
2 2
4 26
Output
11
9449