问题描述

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

输入格式

第一行一个正整数 $T$（$T \leq 100$）。

对于每一组数据：

一个正整数 $n$（$n \leq 2\,000\,000\,000$）。

输出格式

对于每一组数据：

输出 Case #t:，$t$ 表示第 $t$ 组数据。

一个正整数 $m$，满足 $m$ 是最小的正整数可以使 $\sqrt{n \cdot m}$ 为一个正整数。

样例输入

2
2
4

样例输出

Case #1:
2
Case #2:
1

提示