After a terrible start against MI, CSK had managed a reasonable total from their 20 overs. Now it was the turn of the bowling department, and they did their best by keeping MI at the same score. The match is tied and a Super Over is due. Who could it be for CSK other than ‘The Sir’ himself? So Sir Jadeja has got the responsibility to bring CSK home. But Sir has a strange way of scoring runs. He scores runs only in 2s, 4s, and 6s (that’s why we call him Sir :p). He wonders if there were N balls to face, in how many ways he can score runs such that the difference of number of runs scored on consecutive balls is at max two. Help Sir to solve the mystery and make the bowlers feel some hard time on the field.

Input

First line contains an integer T, the number of test cases. T lines follow,  each containing an integer N, 1 <= N <= 50.

Output

An integer which is the required answer.

Example

Input:
2
2
3

Output:
7
17