URI Online Judge | 1776

Prom

By Mário Henrique, UFPE BR Brazil

Timelimit: 2

The class of Computer Science of CIn-UFPE 2025.1 is graduating! It is a very special graduation, not only because all major projects of students in this class have become multinational corporations, but also because the number 2025 is a perfect square! Therefore, the students decided to make all numbers of the ceremony a perfect square: dates, number of guests, hash of the name of the class, the amount of students graduating, etc.

The party organizers were able to meet this requirement until the time comes to buy the snacks. They came into boxes with N snacks at a time. If N is not a perfect square, they will have to buy more than one box. Help the party organizers by making a program to calculate the minimum number of snacks they should buy to meet the eccentric requirements of the students.

Input

The first line contains an integer T (1 ≤ T ≤ 1000), the number of test cases. Each of the next T lines contains an integer N (1 ≤ N ≤ 10⁹), the number of snacks that comes in a single box.

Output

For each test case print a line with "Caso #X: Y", where X is he number of the current case, starting with 1, and Y is the minimum number of snacks that the party organizers should buy.

Input Sample Output Sample

5
5
9
10
12
13

Caso #1: 25
Caso #2: 9
Caso #3: 100
Caso #4: 36
Caso #5: 169