beecrowd | 2080

Röntgen Sequences

By XII Maratona de Programação IME-USP, 2008 BR Brazil

Timelimit: 1

Wilhelm Conrad Röntgen was a German physicist who lived in the late 19th and early 20th centuries. His experiences in electromagnetic radiation earned him the first Nobel Prize in Physics, awarded in 1901. His main finding was the existence of the "X-ray" and its use in medical applications. On December 22, 1895, Röntgen did an x-ray of the hand of his wife (with a ring on one of her fingers). The discovery of X-rays caused a stir at the time and already in 1896 European papers reported the invention and the great possibilities of looking inside the body without having to cut it. Röntgen's death, caused by a certain type of cancer is attributed to the constant radiation to which he was exposed during his scientific researches.

Röntgen began to suspect the existence of invisible radiation when, in his research, he was able to measure significant changes in the fluorescence of objects when placed in a Lenard tube who was subjected to an electric current. Röntgen's studies were so accurate that it could even generate the sequence that was observed in the Lenard tube at each instant of time. The observed fluorescence depended on the intensity of the electric current (X) and the time at which the tube was subjected to electric current (Y). Röntgen realized that given the first sequence, the next could be obtained describing the numbers of the previous sequence. For example, if the first sequence is 2 then the next is 12 (ie, the previous sequence is formed by " a 2"), the following 1112 (ie, the previous sequence is formed by an 1 and a 2), 3112 (ie, the previous sequence is formed by three 1 and a 2), and so on.

Besides a brilliant scientist, Röntgen was extremely organized. He kept all records of his experiments. Unfortunately, over time some sequences were damaged and others lost. Your task is given a sequence, determine the next K sequences of the experiment.


The input is composed of several instances. The first line of input contains an integer T indicating the number of instances.

Each instance consists of a line containing the first sequence of the experiment, consisting of no more than 1000 characters from 0 to 9, and the K number of sequences we wish to generate (1 ≤ K ≤ 50), respectively.


For each instance, print the sequence given in input followed from K lines containing the sequences in the order they were generated. The sequences generated will not have more than 2000000 characters.

After each instance print a blank line.

Sample Input Sample Output

2 5
99 3
000123 3