Self-Replicating Numbers

Sherlock is fond of playing with numbers. Two days ago he discovered that 9376^2 = 87909376 - the last four digits constitute 9376 again. He called such numbers self-replicating.

More precisely, an n-digit number is called self-replicating if it is equal to the number formed by the last n digits of its square. Now Sherlock often asks Xay to help him to find new such numbers. To make the things worse, Sherlock already knows what the scales of notation are, so he asks Xay to find, for example, hexadecimal or binary self-replicating numbers.

Xay wants to help Sherlock, but unfortunately he is very busy now: he is seriously preparing and training for the next ACM Regional Contest. So he asked you to write a program that for a given base b and length n will find all n-digit self-replicating numbers in the scale of notation with base b.

there are multiple test cases. one line of each test case contains two integer numbers b and n separated by a single space, the base b of the scale of notation (2 ≤ b ≤ 36) and the required length n (1 ≤ n ≤ 2000).

For eacho test case, the first line contains K - the total number of self-replicating numbers of length n in base b. Next K lines contain one n-digit number in base b each. Uppercase Latin letters from A to Z must be used to represent digits from 10 to 35. The self-replicating numbers should be output int lexicographic order.

2 1
10 4

2
0
1
1
9376

2009 Multi-University Training Contest 3 - Host by WHU