wavy-ranges

Learning about all the sinusoidal functions of trigonometry, Rahul has grown fond of numbers, whose digits increase and decrease alternatively.  

Let's call d[i] is the i^th digit of a number d. Formally, a wavy number is defined as a number d such that either d[0] < d[1] > d[2] ... or d[0] > d[1] < d[2] ...  

Given a number N, can you find the integers L and R such that the range [L, N] and [N, R] each contain exactly K wavy numbers. Also, these ranges should be as large as possible.

Note that if no L ≥ 1 is found or the required value of R exceeds 10^18, you should output -1.

Input:
The first line of input file contains T, the number of test cases to follow.
Each of the following T lines contain two space-separated integers N and K.

Output:
Output exactly T lines, each containing two integers L and R sepated by a single space.

Constraints:
1 ≤ T ≤ 625
1 ≤ K, N ≤ 10^18

SAMPLE INPUT
2
9 2
2 3

SAMPLE OUTPUT
8 11
-1 4

Explanation

Case 1:
[8, 9] has 2 wavy numbers 8 and 9.
[9, 11] has 2 wavy numbers 8 and 10. Note that [9, 10] also has 2 wavy numbers but its size is not maximal.

Case 2:
Note that for no value of L ≥ 1 we can have a range that has 3 wavy numbers and the range ends at 2. So, value of L is -1. R is simply 4 as [2, 4] contains 3 wavy numbers 2, 3 and 4.

Source: hackerearth | Difficulty: HARD
Tags: Dynamic programming


Solutions: