Image a two dimensional grid. Starting from the origin (0, 0), you have to find out how many ways to move back to the origin after K steps. In each step, you may move to those adjacent points in four directions, right, left, up, down, and you may visit the points more than one times during a walk. Two walks are considered different if not all of the points they visit in each step are the same.
The first line of the input is an integer Z (Z ≤ 10), denoting the number of test cases that follows.
Each test case contains only a single integer, which is the number K (K ≤ 20) defined in the problem description.
There will be a leading blank line for each test case in the input.
For each test case, output a line containing the test case number (starting from 1) and number of possible walks. The detailed format is shown in the sample output, and note that there is a single space character before the sharp sign and after the colon.