Migrated from Lutece 1246 拆拆拆~

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你一个数x，你有两个操作

1.分解质因数，如果x是一个合数，那么就将x分解质因数，然后进入操作2，否则输出这个数

2.将分解质因数中的乘号变成加号，执行操作1

问你最后输入多少？

Input

多组数据，大概10000组，每组数据仅包含一个正整数n(1<=n<=10^9)

Output

对于每组数据，输出一个整数，表示最后的数字。如果无法得到最后的数字，输出-1

Samples

1
2
4
6
8
10

1
2
-1
5
5
7

Note

1,2都不是合数

4=2^2=2*2, 2+2=4,陷入了死循环，输出-1

6=2*3,2+3=5,写出5

by qscqesze

Resources

每周一题