ICPC North America Qualifier 2016, Problem F

Quido has lunch in Hugo's restaurant every day. He likes the restaurant because all of its prices are expressed as integers, and for each possible price (i.e. ~$1~, ~$2~, ~$3~, etc.) there is at least one beverage and at least one main dish on the menu. Every day there are three entries printed on Quido's lunch bill: the beverage price, the main dish price, and the total price. Hugo knows of Quido's interest in computational problems and he offered Quido a free dessert each time his lunch bill meets the following three constraints:

• the bill is not identical to any of Quido's previous bills,
• the price of the beverage is less than the price of the main dish, and
• the prices listed on the bill cannot mutually use the same digit. In essence, any digit which occurs in any of the entries (beverage, main dish, total) must be different from any of the digits of the other two entries.

Quido is on a budget and he pays the same price for his lunch every day. How many times can he have a free dessert?

Input Specification

The input consists of a single line with one integer representing the price ~P~ which Quido pays for each lunch. The value of ~P~ is positive and less than ~10^{18}~.

Output Specification

Output the maximum number of times Quido can have a free dessert at Hugo's restaurant, provided that the price of his lunch is always ~P~. Next, the possible bills which result in a free dessert are listed in ascending order with respect to the beverage price. Each bill consists of the price of the beverage followed by the price of the main dish. For simplicity, the value ~P~, which is always the same, is not included in the bill.

If there are more than ~5000~ possible bills, then output only the first ~5000~ bills (but still report the total number of possible bills before the list of bills).

Sample Input 1

37

Sample Output 1

4
8 29
9 28
11 26
15 22

Sample Input 2

30014

Sample Output 2

7
85 29929
88 29926
785 29229
788 29226
7785 22229
7788 22226
7789 22225

Sample Input 3

202020202020202058

Sample Output 3

3
7676767676767667 194343434343434391
37373737373737397 164646464646464661
67676767676767667 134343434343434391