Chandler wants to give Joey money as Joey is going through some financial struggles. He believes 1500 will be enough to pay off the bills. Chandler makes up a game on the spot called "Cups", which has no rules. Every move Joey makes in the "game", Chandler says that he wins a lot of money. Joey, being "smart", finds this out and thus wants to set some rules.

Joey and Chandler have a set of cards, where the value of a card is defined as the product of all the digits of the number printed on that card.

For example, value of the card with the number 7 equals 7, value of the card with the number $203 equals 2 \cdot 0 \cdot 3 = 0$.

The initial number on Joey's card is N (without any leading zeroes). Chandler can make at most K changes on the digits of the number before it gets noticed. In one change, he can choose any digit x (x ≠ 9) of the number printed on card and replace it with x+1.
Find the maximum possible value of Joey's card after making the changes.

------ Input Format ------

• First line will contain T, number of testcases. Then the testcases follow.
• For each test case, given two integer N and K, denoting the initial number on Joey's card and the number of changes Chandler can make.

------ Output Format ------

For each testcase, output in a single line the maximum possible value of Joey's card after making the changes.

------ Constraints ------

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{6}$
$0 ≤ K ≤ 10^{6}$

----- Sample Input 1 ------
3
1 5
2221 3
123456 0
----- Sample Output 1 ------
6
36
720
----- explanation 1 ------
Test case 1: Chandler can increase the digit $1$ five times to make the final number on card $6$.

Test case 2: Chandler can increase the first digit of the given number once and the last digit twice. After making these changes, the final number on the card would be $3223$, whose value is equal to $36$. There are other ways to make changes on the printed number which may lead to one of the following numbers being the resulting number on card : $2233$, $2323$, $2332$, $3232$, $3322$; note that all these numbers have their values equal to $36$ as well.

见题面

见题面