Vasya's younger brother Misha is fond of playing with numbers. Two days ago he discovered that 9376 ² = 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 Misha often asks Vasya to help him to find new such numbers. To make the things worse Vasya's brother already knows what the scales of notation are, so he asks Vasya to find, forexample, hexadecimal or binary self-replicating numbers.
Vasya wants to help his brother, 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.