It is known that Petka is fond of arithmetic. Many times he thought of a positive integer and gave Chapaev the sum of its digits and the sum of its squared digits, and Chapaev could always find the smallest number with these properties very quickly. But Chapaev's answer never was the number Petka had in mind. What could be done about that? What number should Petka think of so that Chapaev would find just it?

Petka asked Furmanov to teach him how to determine whether a number was the smallest one with the given sums of digits and squared digits. Furmanov was interested in the problem. After some thought, he understood that the sums didn't depend on the order of digits. Therefore, the digits in a “smallest” number were always in ascending order, and there could be no zeros in such numbers. Taking the problem seriously, he found out the following property: if some digits were deleted from a “smallest” number, one that was left was also a “smallest” number.

Then Furmanov understood that he could write several patterns that would specify all the numbers Petka was interested in. It was sufficient to use such patterns in which there would be asterisks in addition to digits, each asterisk meaning that the preceding digit could appear in this place an arbitrary number of times (including the case when it would be absent).

Furmanov took yesterday's copy of the Pravda and wrote a list of patterns on the margins. His list was such that for any “smallest” number there was a pattern matching it and any number matching any pattern was “smallest”. Moreover, the list was the shortest possible. Can you repeat Furmanov's heroic deed?

You are given the base of the number system for which it is required to make the list (the base is in the range from 2 to 36).

Output the list of patterns sorted in the usual ascending order. Each pattern may contain only digits of the given number system (1, 2, …, 9, A, B, …) and an asterisk. The patterns should not contain unnecessary elements: instead of the pattern “12*2*3” you should output “12*3”. It is allowed that the empty string matches several patterns.

The numbers 222 and 1113 have the same sum of digits and the sum of squared digits. That is why any number containing three ones and one three can be “lessened” with the sums of digits and of squared digits preserved.