+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Iran is the country of art and music. There are many Iranian poets and musicians in the world. But none of them are better than Reza Shiri. He is our most favorite singer in SBU. Not only good at singing, Reza is also good at algorithms and mathematics. He has created a problem for Newbies2018 and if you solve it. You may win a ticket to his concert (I wish I had this chance). A number is 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, \quad 6 = (20)_3, \quad 31 = (1011)_3$$ Checking whether a number is prime-lover or not is too easy task for you to win a ticket. So, I changed his problem a little. Given two integers $N, K$. Can you calculate $K$’th smallest prime-lover which is not greater than $N$? # ورودی 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 \leq N, K \leq 10^{13}$$ # خروجی For each test case, print the answer to the problem. If there is no such number, print $-1$. # مثال‌ها ## ورودی نمونه ۱ ``` 3 10 3 10 6 10 7 ``` ## خروجی نمونه ۱ ``` 5 10 -1 ``` Prime-Lover Numbers not greater than $10$ are: $2, 4, 5, 6, 7, 10$ $$2 = (2)_3, \quad 4 = (11)_3, \quad 5 = (12)_3, $$ $$6 = (20)_3, \quad 7 = (21)_3, \quad 10 = (101)_3$$