Description

任何一个整数，都可以有多个素数相乘， 现在给你一个数N(1< N<=65535)， 请你把它分成多个素数相乘。

Input

输入一个整数N，输入0表示结束.

Output

输出相应的结果.

Sample

Input

2
12
16
65535
0

Output

2
2*2*3
2*2*2*2
3*5*17*257

Source: hxx