BUYINT - Buying Integers

Let's assume that you have n integers, A1, A2, A3 ... An.

Let's define:

  • E = Number of pairs (i, j) such that i < j and (Ai + Aj) are even.
  • O = Number of pairs (i, j) such that i < j and (Ai + Aj) are odd.
  • D = | E-O | (That means, D = (E-O) if (E-O) ≥ 0, -(E-O) otherwise.)

Unfortunately, you do have n but those n integers are lost. You will have to buy them again. Before going to the market, you have decided that you will buy n integers in such a way that the value of D will be as small as possible, as you will have to pay D golden coins to buy them.

Now, you are wondering, what that minimum D will be. (Let's call it Dmin).

Input

First line of the input file will contain the number of test cases, T ≤ 1000000, followed by T lines, each containing an integer n (1n109).

Output

For each case, print the case number starting from 1 and Dmin for the value of n in that particular case. See the sample output for exact formatting.

Example

Input:
3
3
4
5

Output:
Case 1: 1
Case 2: 0
Case 3: 2

Warning: Input file is huge, please use faster input and output methods (e.g. printf and scanf in C++).

Problem Setter: Momontho Mashak Monmoy

Special Thanks: Muhammad Ridowan


Added by:Faiyaz
Date:2013-12-24
Time limit:1.277s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2024-02-28 07:21:22
Beautiful problem, but, please just output a newline for every case, for example printf("Case %d: %lld\n",ti+1,res). Costed me 2 wrong answers just because I skipped a newline "\n" character at the end of my presentations.
2015-12-12 22:54:46 Shashank Tiwari
@Bhavik , Numbers can be same or even 0 or negative. But they will be integers always.
2014-01-02 17:54:35 Labib666
Is exact formatting as the sample output maintained for judge results?
My output had an empty line between the outputs and I kept getting WA. But now the newline is removed and it's AC!

Reply:
There is no blank line between testcases in sample output

Last edit: 2014-01-07 15:07:48
2014-01-02 08:24:36 Bhavik
can numbers be same?? i mean can we choose numbers 1,1,2,2 or they need to be different?

Last edit: 2014-07-08 16:55:51
2014-01-02 08:24:36 shiv prasad chabarval
@ahmad faiyaz :: if we took all d numbers in descending order then always D=0 :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.