## 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 ≤ 10^{13})

### 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 7Output: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 |