This is the hard version of the problem. The easy version differs from the hard one in that it requires determining the minimum cost with the least number of deals, while the hard version requires determining the minimum cost with a limited number of deals.

After the cunning seller sold three watermelons instead of one, he decided to increase his profit — namely, he bought even more watermelons. Now he can sell $$$3^x$$$ watermelons for $$$3^{x+1} + x \cdot 3^{x-1}$$$ coins, where $$$x$$$ is a non-negative integer. Such a sale is called a deal.

A calculating buyer came to him, but he has little time, so the buyer can make no more than $$$k$$$ deals and plans to buy exactly $$$n$$$ watermelons.

The buyer is in a hurry and has therefore turned to you to determine the minimum number of coins he must pay the seller for $$$n$$$ watermelons if he makes no more than $$$k$$$ deals. If it is impossible to buy exactly $$$n$$$ watermelons while making no more than $$$k$$$ deals, output $$$-1$$$.

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases. The description of each test case follows.

In a single line of each test case, there are two integers $$$n$$$ and $$$k$$$ $$$(1 \le n, k \le 10^9)$$$ — how many watermelons need to be bought and how many deals can be made.

Output

For each test case, output a single integer — the minimum cost of the watermelons or $$$-1$$$ if it is impossible to buy the watermelons while meeting all the conditions.

Note

Note that there is no point in buying more watermelons than needed, so we will not consider deals where there are more watermelons than necessary.

Let's consider the costs of the first two deal options:

Deal A: $$$1$$$ watermelon — $$$3$$$ coins.

Deal B: $$$3$$$ watermelons — $$$10$$$ coins.

In the first sample, the only way to buy $$$1$$$ watermelon is to use Deal A, so the answer is $$$3$$$.

In the second sample, you can buy $$$3$$$ watermelons either with Deal B for $$$10$$$ coins or with three Deal A for $$$9$$$ coins, so the answer is $$$9$$$.

In the third sample, there are the following options for $$$3$$$ deals:

$$$3$$$ Deals A — $$$3$$$ watermelons.

$$$2$$$ Deals A and $$$1$$$ Deal B — $$$5$$$ watermelons.

$$$1$$$ Deal A and $$$2$$$ Deals B — $$$7$$$ watermelons.

$$$3$$$ Deals B — $$$9$$$ watermelons.

It can be seen that it is impossible to buy exactly 8 watermelons.

The Cunning Seller (hard version)

Examples