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
| Sample Input | Sample Output |
|---|---|
3 1 2 3 | Case 1: 36 Case 2: 210 Case 3: 1350 |