I. Digit insertion
time limit per test
0.25 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

At a Poupatempo service center in São Paulo, there is a self-service kiosk that, among many other pieces of information, requires users to enter their mobile phone number. Unfortunately, the system does not verify whether the entered phone number is valid, so users may enter any sequence of 1 to 20 digits, and the system will accept and store it.

To make matters worse, Poupatempo employees noticed that the digit keys most commonly used when entering mobile phone numbers, namely 1 and 9, have started to malfunction. When a user presses 1 or 9, there is a chance that the key press is not registered, causing the number to be saved without that digit.

Poupatempo has hired you to develop a program that, given a phone number stored for a user, prints all possible valid mobile phone numbers from the state of São Paulo that the user may originally have entered, considering that the 1 and 9 keys may have failed while the user was using the kiosk.

A mobile phone number from the state of São Paulo is considered valid if it consists of 11 digits, starting with two digits representing one of São Paulo's valid area codes (DDDs), followed by the digit 9, and then followed by any 8 additional digits.

The list of valid São Paulo area codes is:

  • 11: São Paulo (capital), Greater São Paulo (Guarulhos, Osasco, ABC Paulista, etc.), and the regions of Jundiaí and Mogi das Cruzes.
  • 12: Vale do Paraíba, São José dos Campos, Taubaté, Guaratinguetá, and the northern coast.
  • 13: Baixada Santista, Santos, São Vicente, Guarujá, Praia Grande, and the southern coast.
  • 14: Bauru, Marília, Botucatu, Ourinhos, and Jaú.
  • 15: Sorocaba, Itapetininga, and surrounding areas.
  • 16: Ribeirão Preto, Franca, Araraquara, and São Carlos.
  • 17: São José do Rio Preto, Catanduva, and Votuporanga.
  • 18: Presidente Prudente, Assis, Dracena, and Araçatuba.
  • 19: Campinas, Piracicaba, Limeira, Americana, and Rio Claro.

For example, if the stored number is 11983609574, then the only valid number the user could have entered is the stored number itself. However, if the stored number is 1922222222, then there are two valid phone numbers that the user could originally have entered: either 19922222222, if the third digit failed to register, or 11922222222, if the second digit failed to register.

Input

The input consists of a single line containing a sequence of 1 to 20 digits, each between 0 and 9.

Output

The first line should contain the number $$$N$$$ of possible valid phone numbers.

The next $$$N$$$ lines should each contain one possible valid phone number.

The phone numbers must be printed in increasing order.

Examples
Input
1922222222
Output
2
11922222222
19922222222
Input
10913574286
Output
0
Input
23456789
Output
17
11923456789
12913456789
12931456789
12934156789
12934516789
12934561789
12934567189
12934567819
12934567891
12934567899
12934567989
12934569789
12934596789
12934956789
12939456789
12993456789
19923456789