Limits 1s, 512 MB

Meena is a talented girl in her class. She likes to brainstorm in her leisure times. One day, she was observing a calendar. Suddenly, a thought crossed her mind. It was about making a mathematical problem using month, day and year. As Meena is a talented girl, she has made and solved her own problem successfully. Will you be able to solve her problem?

In Meena’s problem, at first, she takes three types of paper. The types are D, M and Y. In D paper, she writes a day. In M paper, she writes the number of a month and in Y paper, she writes a year. While writing, she doesn’t put any leading zeros. After that, she takes the values written on the papers D, M, Y one by one, merges them and converts it to a string S. She doesn’t violate the order: D, M, and Y. That is to say, the first portion of the string S is from the paper D, the next portion is from the paper M and the last portion is from the paper Y. For example, if Meena wants to write the 25th day of the 3rd month of year 724 in the papers, she will write 25 on paper D, 3 on paper M and 724 on paper Y. After merging and converting them to string S, the string S will be “253724” (without the quotes). This is the one and only way of constructing string S. Now, you will be given the length of the string S. You have to find out how many strings S of the given length are palindrome if you construct S according to the way stated above.

A Palindrome is a string that reads the same backward as forward. “17122171”, “91033019” are some valid palindromic strings of length 8 here. In the first string, 17 is the day, 12 is the month number and 2171 is the year. In the second string, 9 is the day, 10 is the month number and 33019 is the year.

There are 300 days in a month and 26 months in a year on the planet of Meena and counting of day, month and year start from 1. That is to say, the first date of the history of her planet is: day 1, month 1, year 1. And so, 1 <= D <= 300, 1 <= M <= 26 and Y will contain any positive numbers. It is possible to construct same string S from different values of D, M, Y such as: string S = “2112” can be constructed from D = 2, M = 1, Y = 12 or from D = 21, M = 1, Y = 2 etc. In such cases, they will be considered as different strings though the values of the strings are the same.

Input

Input will start with an integer T, the number of test cases.
In each test case, there will be an integer N – the length of the string S.

Constraints:
1 <= T <= 100
1 <= N <= 105

Output

For each test case, output a single line containing (without the quotes) "Case x: y", where x is the case number and y is the number of possible palindromic string S of the corresponding length given in input. As y can be very big, print y mod 1000000007.

Sample

InputOutput
4
4
3
7
21
Case 1: 180
Case 2: 81
Case 3: 19413
Case 4: 696298656

Submit

Login to submit.

Statistics

94% Solution Ratio
solaimanopeEarliest, Oct '19
Kuddus.6068Fastest, 0.0s
mahdi.hasnatLightest, 131 kB
user.2599Shortest, 1509B
Toph uses cookies. By continuing you agree to our Cookie Policy.