Meeting Place

There is an N*N grid where (r,c) denotes a cell number where r means row number, c means column number. You are in the (0,0) cell and your friend is in the (N, N) cell. You start from (0,0) and want to reach (N,N). Your friend starts from (N,N) and wants to reach (0,0). You can only move upward or right direction and your friend can only move downward or left direction.

You both start your journey at the same time. In each second you both move following the rules described before. Your journey ends at (N,N) and your friend's journey ends at (0,0). Both of you may meet at the same point during your journey.

Let's define a function F(x,y) = Number of ways you and your friend can meet at cell(x,y). Two ways are different if at least one of you or your friend's path from starting cell to meeting cell is different.

You have to determine: G(N)

You will need to print G(N) modulo 999377

For clarification, if you are at the (r,c) cell you can only move to (r+1,c) or (r,c+1) cell at one step. if your friend is at the (r,c) cell he can only move to (r-1,c) or (r,c-1) cell at one step.

Input

The first line of the input will contain an integer T where T<=10000, denoting the number of test cases. Then there will be T test cases. Each of them containing one integer N where 1<=N<=1000000000000, denoting the row size and column size of the grid.

Output

For each test case, you have to print "Case x: y" without quotations where x will denote the case number and y will denote the required answer modulo 999377.

Sample

2
1
2

Case 1: 2
Case 2: 6