E. Great Product
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Armando is a very curious child; he always gets obsessed with something different, and now, he is obsessed with numbers. In particular, he is very interested in the fact that many natural numbers can be represented as the product of smaller numbers. For example, $$$2002$$$ can be represented as $$$14 \times 143$$$; $$$2880$$$ can be represented as $$$2 \times 2 \times 16 \times 45$$$.

He also realized that he can add an infinite number of ones to any number and it will still be the same number ($$$2002 = 14 \times 143 \times 1 \times 1 \times ...$$$). This seems absurd to him, so he decided never to use ones in his representations.

Now he wonders: What is the representation of a number $$$n$$$ as a product of smaller or equal numbers that uses the largest number of factors possible without using ones?

You must help him find this product. To make it easier for Armando to understand the answer, you should print the factors in non-decreasing order and separate each one with the letter 'x' (lowercase 'x', without quotes).

Input

The first and only line contains an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$).

Output

A line with the factors in non-decreasing order, separated by the letter 'x'.

Examples
Input
12
Output
2x2x3
Input
5
Output
5
Input
94202
Output
2x19x37x67
Note

In the first example, $$$12$$$ can be represented as $$$4 \times 3$$$, $$$12$$$, $$$2 \times 6$$$ or $$$2 \times 2 \times 3$$$. The answer is $$$2 \times 2 \times 3$$$ because it is the representation with the most factors.