Description

废话少说，给你一个大数 $N$（可能大于 $4 \times 10^7$），让你进行素性判断，然后分解质因数。当然，初中数学题不可能有大于 $4 \times 10^7$ 的数让你判断素性，因此超过范围的数可以忽略不计。为了让程序更加贴心，JosephZheng 多了一些要求，会在输入输出中给出具体情况。

Input Format

一个大数 $N$（$N$ 为非负整数），其中这个数的各个数位之间可以插入各种符号（包括负号和小数点等，它们也需要被忽略），例如 $1234$ 可以为 1 - 2alsdkjf3！@￥%！@@@##￥……！￥#-4 等。你需要在这一长串乱码中找出这个要判断的数。

输入数据可能有多组，如果读到一行没有数字的字串即结束。

保证输入数据不超过 $100$ 组，字符串长度不超过 $1000$。

Output Format

在读入数据之前先输出 Enter the number=，需要换行。

然后输出 Prime?，问号后有一个空格，但不要换行。

如果是质数则输出 Yes! 否则输出 No!。此时换行。

若果是质数就 halt，若是小于 $2$ 的数则在输出 No! 后也 halt。

若是合数则分解质因数。如果该数大于 $4 \times 10^7$ 则输出 The number is too large!，然后 halt。

否则分解质因数。

输出结果的方式在输出样例中会详细给出。

每组数据之间空一行。

（halt：停止处理本组数据）

4
eed

Enter the number=
Prime? No!
4=2^2

Enter the number=

2
end

Enter the number=
Prime? Yes!

Enter the number=

-1
adfs

Enter the number=
Prime? No!

Enter the number=

1234###24#@13#@￥！1
hehe

Enter the number=
Prime? No!
The number is too large!

Enter the number=

1.5
1
1234324123512343123
@~@~@~@

Enter the number=
Prime? No!
15=3^1*5^1

Enter the number=
Prime? No!

Enter the number=
Prime? No!
The number is too large!

Enter the number=

12
halt@@

Enter the number=
Prime? No!
12=2^2*3^1

Enter the number=

Hint

编这道题的 JosephZheng 有些无聊，但是很考验基本功哦！仔细审题！

水题一道。。。