Codah ClubUshtrohu. Dërgo. Përmirësohu.
Hyr
Shqip
#000721

P-Collatz

A well-known comic on xkcd says the following:


"The Collatz conjecture states that if you pick a number, and if it's even divide it by two and if it's odd multiply it by three and add one, and you repeat this procedure long enough, eventually your friends will stop calling to see if you want to hang out."


Little Perica, being a great fan of xkcd, wanted to try out this theory. So he started randomly picking natural numbers and applying the Collatz function described above a certain number of times. The results were clear; his friends eventually stopped calling him. And now he has a problem - he wrote down a final value after executing the function K times, but he can't remember which value he started with. Since all his friends have abandoned him, he turned to you. Help him determine the smallest possible value he could have started from.


InputThe first line of the standard input contains a natural number T (1 <= T <= 500000), the number of testcases. Each following line of the standard input contains two integers X (1 <= X <= 5 * 10^10) and K (0 <= K <= 24).

OutputWrite to the standard output the smallest possible initial number N for each test case, such that when executing the Collatz function K times on it we get the number X.

Input:
1
5 7
Output:
17
Explanation: Starting from 17, we get the following values by repeatedly applying the Collatz function: 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5. There is no smaller number than 17 that produces 5 in the end.

Input:
1
99 0
Output:
99

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.