Problem 1107. -- 张老师很强

1107: 张老师很强

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 563  Solved: 73
[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]