In 1955, the mathematician D. R. Kaprekar discovered an interesting property:

For any 4-digit positive integer where not all digits are the same, if you subtract the number formed by arranging its digits in ascending order from the number formed by arranging its digits in descending order, you will obtain a new 4-digit positive integer (including leading zeros). If you repeat this process, you will inevitably reach the number 6174. Because repeating this process with 6174 results in 6174 itself, this property is like a black hole from which there is no escape, and thus 6174 is known as a "black hole number."

For example: $2024 \rightarrow 4220 - 0224 = 3996$ $3996 \rightarrow 9963 - 3699 = 6264$ $6264 \rightarrow 6642 - 2466 = 4176$ $4176 \rightarrow 7641 - 1467 = 6174$ $6174 \rightarrow 7641 - 1467 = 6174$

This gives: $2024 \rightarrow 3996 \rightarrow 6264 \rightarrow 4176 \rightarrow 6174$

A similar situation occurs for all $d$-digit numbers where not all digits are the same, although they do not necessarily stop at a single number, but may instead cycle between a group of numbers. For example, when $d = 5$, the following are two types of cycles:

$53955 \rightarrow 59994 \rightarrow 61974 \rightarrow 82962 \rightarrow 75933 \rightarrow 63954$

It is not difficult to deduce that regardless of $d$, starting from any number will eventually lead to a cycle of numbers (a single number also counts as a cycle). Given $n$ $d$-digit numbers where not all digits are the same, please output the first number encountered when entering a cycle after performing the calculation steps starting from each given number.

For example, if we start with 50985, after several steps we get the following result. We can see that after 7 steps, we reach 75933, which has already appeared in the previous calculation. Subsequent calculations will enter a cycle, and 75933 is the first number encountered when entering the cycle. Therefore, for this example, 75933 should be output.

$50985 \rightarrow 92961 \rightarrow 86922 \rightarrow 75933 \rightarrow 63954 \rightarrow 61974 \rightarrow 82962$

Input

n d
s1
s2
...
sn

• $n$ is a positive integer, representing the number of queries.
• $d$ is a positive integer, representing that all subsequent numbers to be queried are $d$-digit numbers.
• $s_i$ is a positive integer, representing the starting number for the $i$-th query (excluding leading zeros).

Output

c1
c2
...
cn

• $c_i$ is a positive integer, representing the first number encountered when entering a cycle after performing the calculation steps starting from $s_i$ (excluding leading zeros).

Constraints

• $2 \le d \le 10$.
• $1 \le n \le 10^4$.
• $1 \le s_i < 10^d$.
• All input numbers are positive integers.
• It is guaranteed that for $s_i$, not all digits are the same in its $d$-digit representation.
• It is guaranteed that for the $n$ numbers, the total number of calculation steps to enter a cycle does not exceed $10^5$.

Examples

Input 1

4 4
2024
4167
4266
2024

Output 1

6174
6174
6174
6174

Input 2

3 5
50985
53955
95355

Output 2

75933
53955
59994

Subtasks