A number is called prime-lover, if sum of its digits in base-3 is a prime number. For example 2, 6, and 31 are prime-lovers, sum of digits of all these numbers are prime.

2=(2)₃ ,  6=(20)₃ , 31=(1011)₃

Checking whether a number is prime-lover or not is too easy for this contest, so solve this problem:

Given two integers N, K. Can you calculate K’th smallest prime-lover which is not greater than N?

Input

The first line of input indicates the number of test cases (There will be at most 1000 test cases)

Each test case consists of two space-separated integers N, K. (1 ≤ N, K ≤ 10¹³)

Output

For each test case, print the answer to the problem. If there is no such number, print -1.

Example

Input:
3
10 3
10 6
10 7
Output:
5
10
-1

Prime-Lover Numbers not greater than 10 are:

2, 4, 5, 6, 7, 10