PLOVER - Prime Lover Finding

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)3 ,  6=(20)3 , 31=(1011)3

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 ≤ 1013)

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


Added by:MRM
Date:2018-05-29
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:SBU Newbies Programming Contest 2018

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.