Bajtazar has just graduated from the Bajtocka Pedagogical School and will start working as a kindergarten teacher after the holidays. Since the sight of a man in such a position might be a novelty for many Bajtocka children, he decided to win their hearts with a trick. As soon as he greets his group, he will turn one of his pockets inside out, and candies will spill onto the floor. The children will not allow any candy to remain uneaten, but it is very important to Bajtazar that every child receives an equal number of candies (otherwise, some of them might not like him). Thus, the number of spilled candies must be divisible by the number of children.

It would be extremely simple, but Bajtazar does not know how many children will be in his group. Knowing that his trousers have two pockets and knowing the capacity of a single pocket (i.e., how many candies fit in a pocket), help him choose the number of candies so that he is prepared for as many different possible group sizes as possible.

Input

The first and only line of input contains a single integer $n$ ($n \ge 1$) representing the capacity of a pocket in Bajtazar's trousers.

Output

The first line of output should contain a single natural number — the number of possibilities for which Bajtazar can be prepared. The second line of output should contain two positive integers $x$ and $y$ not exceeding $n$ — the number of candies Bajtazar can place in both pockets to be prepared for that many possibilities. If there are multiple such pairs of numbers, you may output any one of them.

Examples

Input 1

15

Output 1

8
12 10

Note

A pocket with 10 candies makes Bajtazar ready for 1, 2, 5, or 10 children, while a pocket with 12 candies makes him ready for 1, 2, 3, 4, 6, or 12 children. In total, Bajtazar is ready for 8 possibilities (these are 1, 2, 3, 4, 5, 6, 10, and 12).

Subtasks