Given a sequence S of digits and a number K, for example S = "4113" and K = 2. In the sequence S, there is one '4', followed by two '1's, followed by one '3'. Then we can produce a new sequence S' = "142113".
(note: "one 4" -> 14, "two 1s" -> 21, "one 3" -> 13)
This is the first round, and we need to do it for K rounds. The input of the (i+1)-th round is the output from the i-th round. When i = 1, the sequence is the input S. Your task is to print the output after K rounds.
Another example:
S = "323", and K = 1
then we have one '3', followed by one '2', and followed by one '3'. So the next sequence S' would be "131213"
(note: "one 3" -> 13, "one 2" -> 12, "one 3" -> 13)
The input includes multiple test cases.
The first line of the input is an integer T (T <= 1000) specifying the number of test cases. For each case, the first line contains a sequence S. The second line contains one integer K.
Difficulty level 1: length of S <= 5, 1 <= K <= 2
Difficulty level 2: length of S <= 100, 1 <= K <= 2
Difficulty level 3: length of S <= 100, 1 <= K <= 5
Difficulty level 4: length of S <= 100, 1 <= K <= 5
Difficulty level 5: length of S <= 1000, 1 <= K <= 10
For each test case outputs one line, the output after k rounds.