J. Just a Magic Number
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You will be given a number $$$n$$$ $$$(n \lt 10000)$$$. In one move, you must perform the following operation:

1. If $$$n$$$ has less than four digits in its decimal representation, make it a four-digit decimal number by adding leading zeros.

2. Now sort the digits of $$$n$$$ in ascending order and name it $$$p$$$. Then sort the digits of $$$n$$$ in descending order and name it $$$q$$$.

3. Replace $$$n$$$ with $$$\bf{q-p}$$$.

For example, suppose $$$n=523$$$. After the first move, $$$n=5320-0235=5085$$$.

Your task is to output $$$n$$$ after $$$\bf{k}$$$ moves.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ $$$-$$$ the number of test cases.

Each test case is described by two integers $$$n$$$ $$$(0 \leq n \lt 10000)$$$ and $$$k$$$ $$$(0 \leq k \leq 10^{18})$$$ $$$-$$$ the given number and the number of moves you have to perform respectively.

Output

For each test case, output a single integer $$$-$$$ the value of $$$n$$$ after $$$k$$$ moves.

Example
Input
5
523 2
9365 2
3333 1
351 3
5231 7
Output
7992
8172
0
5355
6174
Note

For the first test case, $$$5320-0235=5085; 8550-0558=7992.$$$

For the second test case, $$$9653-3569=6084; 8640-0468=8172.$$$