Chess is a two-player strategy board game played on a 8 x 8 board. Each player begins with 16 pieces where each type of piece moves differently. Player 1 has all the white pieces and player 2 all the black ones, with white being the one to move first and then players take turns alternatingly until the game ends. The game is played on a square board of eight rows and eight columns. The rows are called ranks and are numbered 1 to 8 from bottom to top from white’s perspective. Similarly, the columns are called files and are denoted from a to h from left to right according to white’s perspective. The objective of the game is to threaten the opponent’s king in such a way that escape is not possible, i.e, checkmate the opponent. If a player’s king is threatened, it is said to be in check and the player must remove the king from check on the next move by either moving to a safe square or capturing or blocking the attacking piece(s). The figure shows the starting position for the game of chess.



In this problem, we’ll be considering a slightly modified version of chess with the following rules:

1. The game will be played on a N x N board.



2. The game will consist of exactly 4 pieces - The white king, the black king, and two white rooks. All four pieces must be placed on different squares of the board.



3. Kings can move to any adjacent square (horizontally, vertically, or diagonally), unless the square is outside the board or occupied by a friendly piece or if the move would place the king under check.



4. Rooks can move to any square in the same rank or file, but not by jumping over other pieces. Also, it cannot land on a square occupied by a friendly piece.



5. A piece X is threatened by another enemy piece Y, iff Y can reach X in exactly one legal move.



6. A piece X can capture another enemy piece Y iff X can reach Y in exactly one legal move. On capturing, piece Y is removed from the board and X takes its place. Note that if X is the king, then it cannot capture Y if Y is guarded by an enemy piece. That is the king can never move and put itself in danger where it is attacked by an enemy piece.



7. The two kings cannot ever be in adjacent (horizontally, vertically or diagonally) squares.



8. The objective of the game is to place the four pieces on unique squares of the board in such a way that if it is black’s move, then the black king is attacked and has no legal moves. That is, the black king must be threatened by at least one of the white rooks and has no way to move to a safe square or eliminate the checks (by capturing the attacking pieces if not guarded). Note that it is not necessary for the board configuration to be legal following the exact rules of chess. That is, if N = 8 there might be valid configurations in our modified game that might never appear in a game of chess. Like the figure shown below, which can never occur in a proper game of chess given that it is black’s turn to move, although it would be a perfectly valid configuration in our game.

Given N, you need to count how many ways you can place one white king, one black king, and two white rooks in the chessboard such that the black king is threatened and has no way to escape the threat given it is black’s turn to move. Two configurations are different if either any of the squares contain different pieces or one square contains a piece but the other does not. Note that every square is uniquely represented by its rank and file and hence mirrored or reversed configurations of the same configuration will be considered as different configurations. Also note that the white king, black king, and white rooks are distinguishable but the two white rooks are identical. So in the figure above, if we swap the two rooks, the new configuration will be the same as the old one.

Since the number of ways can be huge, you need to output it modulo 7340033.

Input

The first line contains the number of test cases denoted by T. The next T lines contain the board dimension N.

Constraints

1 ≤ T ≤ 20

1 ≤ N ≤ 10⁵

Output

For each case, output one line. First output the case number then the number of valid ways modulo 7340033. Please refer to the sample i/o for more clarity on the format.

Sample Input

8
1
2
3
4
5
6
7
8

Sample Output

Case 1: 0
Case 2: 0
Case 3: 232
Case 4: 1432
Case 5: 5188
Case 6: 14536
Case 7: 34464
Case 8: 72392

Explanation

For a 8 x 8 board, here are some valid configurations:









For all of these boards, the black king is attacked and has nowhere to go. Also, both the white rooks are placed on the board and the kings are not in adjacent positions.

And here are some invalid ones:









For the first board, the black king can move and capture the attacking white rook thereby removing the check and moving to a safe square. For the second board, although the black king is attacked and cannot capture anything because all the pieces are guarded, the two kings are adjacent which is not allowed. Hence it is not a valid checkmate position. For the third board, it is a stalemate. That is the black king has nowhere to go but it is also not attacked. So no checkmate. For the fourth board, it is checkmate and the black king has nowhere to go. But we haven’t placed both the rooks on the board and hence this is not a valid position.

---

hide comments

	Simes: 2021-05-03 17:19:54 It didn't take long for link rot to break the embedded images. -> That is a valid concern. However it is still working for me, is it broken for you? Simes: yes, none of the images appear, even if I try to open them directly. Edit: although I've just tried on a different computer, and the images appear ok there. [NG]: psetter, please use https://www.spoj.com/uploads/ for all images. -> Addressed! Last edit: 2021-09-02 18:51:18