Look-and-Say Sequences

Consider the sequence of integers

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ...

It is referred to as the look-and-say sequence with seed 1. The seed refers to the first element of the sequence. Each subsequent element in the sequence is generated from its predecessor as follows: group adjacent occurrences of the same digit and then use two digits to indicate, for each group, how many are in it and which digit it contains, respectively.

For example, the seed, 1, is read as “one 1”, which translates to the second element, 11. We read that as “two 1’s”, which translates to the third element, 21. Moving forward to the fourth element, 1211, we read it as “one 1, then one 2, then two 1’s”, which translates to the fifth element, 111221.

Of course, each different choice of a seed results in a different sequence.

Develop a program that, given as input a nonnegative integer j and a positive integer k, produces as output the first k elements of the look-and-say sequence with seed j.

Input Specification

The first line contains a positive integer n indicating how many sequences are to be generated. Each of the next n lines contains two nonnegative integers j and k that describe a sequence, as explained in the preceding paragraph. You may suppose that j will not contain more than 100 digits and more than 9 adjacent occurrences of the same digit.

Output Specification

For each look-and-say sequence described in the input, the program should generate as output a single line containing the elements of that sequence separated by a single space.

Sample Input

1. 5
2. 1 8
3. 22 6
4. 55555333337 4
5. 0 4
6. 34 1

download as text file

Output for Sample Input

1. 1 11 21 1211 111221 312211 13112221 1113213211
2. 22 22 22 22 22 22
3. 55555333337 555317 35131117 131511133117
4. 0 10 1110 3110
5. 34

download as text file