Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8819

Jo'natishlar soni: 714315

Muhokama yozuvlari: 4540

Yangiliklar soni: 97

Yangiliklar izohlari: 1174


So'ngi izohlar

714. Prime Factors
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

Given a natural number N. Lay it on the prime factors.

   Input

   The first line of input contains a single integer (2 ≤ N ≤ 1 000 000 000).

   Output

   For number N of the input data in a single line through the gap carry him the prime factors in the format shown in the examples.

   Do not put extra spaces, otherwise you will get a "Wrong Answer". For example, if N is 4, you need to remove "2 * 2" (no space after the second two).

Samples

Input

Output

1

13

13

2

4

2*2

3

100

2*2*5*5

 

Tayyorladi: Azat Yusupov
Text from: e-olimp.com
Mening urinishlarim(0) Muhokama (0) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(99) Barcha urinishlar(137)