Having a number n, a look-and-say sequence is generated by reading the digits of n as they appear in the number. So, if the number n is 43556777, we would read it as:

One 4 (14)

One 3 (13)

Two 5s (25)

One 6 (16)

Three 7s (37)

So, the next element in the sequence following the number 43556777, would be 1413251637.

Given an initial number n, you are asked to calculate the resulting number after k steps.

Input

The first line of the input contains the initial number n (1 ≤ n ≤ ).

The second line of the input contains the number of steps k (0 ≤ k ≤ 30).

Output

The program should print the resulting number after k steps in the look-and-say sequence when starting with the number n.