Fate it seems is never without a twist for our beloved pirate Captain Jack Sparrow. He had just beaten the infamous Captain Barbosa and got his ship the Black Pearl back. But now that he is about to set sails to conquer all that once belonged to him, he noticed that he is yet to remove one last curse, the curse of Barbosa. Barbosas curse said that Jack would remain stuck within three islands (we must not utter the names, or we will be cursed, too). We call the islands island 1, 2 and 3. Jack would have to start from a particular island, island 1, and get back to it after visiting all these three islands a given number of times. For example if Barbosas curse said that Jack has to visit every island 2 times, one way to do that would be: 1-2-3-1-2-3-1. As you would notice, the island 1 comes three times because you would have to start from there. What makes Barbosas curse even more interesting is that Jack is not allowed to visit the islands in a reverse route if he had already visited them in one route. For example if Jack took the 1-3-2-1-3-2-1 route, Jack is not allowed to take the 1-2-3-1-2-3-1 route. Barbosa has also made sure that Jack cannot stay in the same island and call it a visit, so trips like 1-2-2-3-1-3-1 are not allowed. But we all know that for every curse there has to be a way to undone it. And fortunately for Jack this curse can be removed without making a single trip through the islands. All Jack has to do is: given the number of total visits, he has to count the number of different ways one can make the trips through these three islands. Jack is a pirate you know. He is smart in his pirate way, but he is certainly not a Computer geek. He is hoping that there are some who would read his story and write a program to remove the curse of Barbosa. Input The first line starts with the number of test cases, T (T ≤ 40). Each of the next T lines contains a single integer N (N ≤ 100). Here N is the total number of island visits that Jack has to make. You can assume that N will always be of form 3 ∗ M + 1, where M is the number of times Jack has to visit island 1, 2 and 3. All trips start from island 1, hence we have the added 1 in the 3M + 1 form. Output For each of the test case print one line of output. The output for each test case starts with the test case number, followed by the number of different ways one can visit the three islands. You can assume that the output for each test case will take at most 40 characters. Sample Input 4 4 7 13 76
2/2 Sample Output Case 1: 1 Case 2: 5 Case 3: 138 Case 4: 206459748327350872816