New Fibonacci Sequence

A new Fibonacci sequence is defined as follows: the first four terms are all equal to one, and each subsequent term is the sum of the four preceding terms.

Your task is to find the N-th term of this sequence.

Input

The first line contains the integer T, representing the number of test cases. The following T lines each contain a single integer, representing the index of the term in the sequence you need to find. 1 ≤ T ≤ 1000

Output

Output T lines, each containing the N-th term of the sequence as specified in the input.

Note: The number of digits in each term will not exceed 2008.

Examples