Limits 1s, 512 MB

There are N nodes in a tree. You can start from any node of that tree and you have to come back to the starting node. In that path you have to visit all others the node also. You can visit a node multiple times. But you have to do it as fast as possible. It takes 1 unit time to move from one node to its adjacent node. Suppose the smallest time to travel from any node in the tree and come back that starting node while having visited all others node is T.

In this problem number of nodes N is given. You have to find the minimum value of T for all possible spanning tree of N nodes.

Input

Input starts with an integer T (T <= 100), denoting the number of test cases.

Each test case contains an integer N. (N <= 10^6). N represents number of nodes of a tree.

Output

For each test case print the case number first and then print the result.

Sample

InputOutput
2
1
2
Case 1: 0
Case 2: 2

This problem was authored for CodeMask Championship 2016 and is being hosted on Toph per organizer’s request.

Submit

Login to submit.

Statistics

93% Solution Ratio
Matrix.codeEarliest, May '16
Neri_KuttaFastest, 0.0s
aaman007Lightest, 0 B
bokaifShortest, 60B
Toph uses cookies. By continuing you agree to our Cookie Policy.