You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Description

把一个合数分解成质因数乘积的形式叫做分解质因数，输入一个正整数n，将n分解成质因数乘积的形式 输入：36 输出：36=2 * 2 * 3 * 3

Format

Input

Output

Samples

10000

10000=2*2*2*2*5*5*5*5

36

36=2*2*3*3

87780

87780=2*2*3*5*7*11*19

Limitation

1s, 1024KiB for each test case.