Problem 1107. -- 张老师很强

1107: 张老师很强

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 681  Solved: 93
[Submit][Status][Web Board]

Description

张老师最近在看《最强大脑》节目，然后张老师突然发觉自己原来很强！为什么这么说呢，因为张老师发现给他一个很大的正整数n，他可以一秒找到一个最小正整数m，使√n*m为一个正整数。突然发现自己这么强，张老师已经感觉自己已经可以上天了，计算机都没办法跟他肩并肩。所以请同学们帮忙让张老师清醒一点，告诉他计算机也可以轻松做到这件事情。

Input

第一行一个正整数T(T≤100)
对于每一组数据：
一个正整数n(n ≤ 2,000,000,000)

Output

对于每一组数据
输出Case #t:，t表示第t组数据
一个正整数m，满足m是最小的正整数可以使√n*m为一个正整数。

Sample Input

2
2
4

Sample Output

Case #1:
2
Case #2:
1

HINT




Source

[Submit][Status]