Calculator

A calculator can perform the following operations:

• Multiply the number X by 2.

• Multiply the number X by 3.

• Add one to the number X.

Your task is to find the minimum number of operations required to transform the number 1 into the number N.

Input

The input consists of a single natural number N, which is no greater than 10^6.

Output

On the first line of the output, print the minimum number of operations needed. On the second line, display the sequence of numbers obtained by performing these operations, starting with 1 and ending with N. If there are multiple valid sequences, you may print any one of them.

Examples