西元 1955 年，數學家卡布列克 (D. R. Kaprekar) 發現了以下有趣的性質：

對於所有位數不完全相同的 4 位數正整數，將其所有位數依數值由大至小排列所得到的數字減去由小至大排列所得到的數字，如此一來會得到另外一新的 4 位數正整數（包含前導零）。若重複上述步驟若干次，必定可以得到 6174 這個數字。又因為以 6174 重複上述步驟計算將會得到 6174 自身，該性質如同黑洞一般只進不出，故 6174 因此而得名「黑洞數」。

舉例來說： $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$

可得： $2024 \rightarrow 3996 \rightarrow 6264 \rightarrow 4176 \rightarrow 6174$

針對所有位數不完全相同的 $d$ 位數，也有類似的情況，只是最後不一定會停在單一一個數字，而是有可能在一群數字之間循環。例如當 $d = 5$ 時，以下是某兩種循環的情形：

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

不難推論，不論 $d$ 為何，由任一數字開始必定會進入某些數字組成的循環之中（單一數字亦算作循環）。今給定 $n$ 個所有位數不完全相同的 $d$ 位數，請各自輸出由該數字作為起始數字進行若干步驟計算後，進入循環時第一個遇到的數字。

舉例來說，若以 $50985$ 作為起始數字進行若干步驟計算後可以得到如下的結果，可以發現到在經過 7 次步驟之後，會得到於先前計算中已經出現過的 $75933$，之後再進行計算將會進入循環之中，而 $75933$ 即為進入循環時第一個遇到的數字，故以本例子來說須輸出 $75933$。

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

输入格式

n d
s1
s2
...
sn

• $n$ 為一正整數，代表接下來欲詢問 $n$ 個數字。
• $d$ 為一正整數，代表接下來欲詢問的數字皆為 $d$ 位數。
• $s_i$ 為一正整數，代表第 $i$ 個詢問的起始數字（不含前導零）。

输出格式

c1
c2
...
cn

• $c_i$ 為一正整數，代表以數字 $s_i$ 作為起始數字進行若干步驟計算後，進入循環時第一個遇到的數字（不含前導零）。

数据范围

• $2 \le d \le 10$。
• $1 \le n \le 10^4$。
• $1 \le s_i < 10^d$。
• 所有輸入的數皆為正整數。
• 保證 $s_i$ 在 $d$ 位數表示中所有位數不完全相同。
• 保證 $n$ 個數字進行若干步驟計算，進入循環時其總計算步驟數不超過 $10^5$。

样例

样例输入 1

4 4
2024
4167
4266
2024

样例输出 1

6174
6174
6174
6174

样例输入 2

3 5
50985
53955
95355

样例输出 2

75933
53955
59994

子任务