Given N and K, find the smallest and the largest positive integers, each with exactly N digits and having exactly K distinct digits (0 - 9). Leading zeroes are not allowed !

Input

First line contains T, the number of test cases (about 200). Each of the next T lines contains 'N K', where 1 <= N <= 18 and 1 <= K <= 10. Input is given such that the answer will always exist.

Output

For each test case, output the two numbers, separated by a space, in a new line. 

Example

Input:
2
1 1
3 3

Output:
1 9
102 987