Server Time: Wed Feb 26, 2020 1:19 pm
Welcome ( logout
E - Kings in Chessboard
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

A regular King in a chess board can attack all its adjacent 8 cells (vertical, horizontal or diagonal). Now you are given a 10 x n chessboard, your task is to place exactly two kings in each column such that no king attacks another. You have to report the number of ways to do that.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 109).

Output

For each case, print the case number and the number of ways to place kings in the chessboard such that no king attacks another and every column contains two kings. Print the result modulo 232.

Sample Input

Output for Sample Input

3

1

2

3

Case 1: 36

Case 2: 210

Case 3: 1350

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan