Everybody knows about the fibonacci numbers. Similar to a fibonacci number, a tribonacci number is the sum of the last three tribonacci numbers. Suppose the initial three tribonacci numbers are 0, 0, 1 then the next terms in the series will be 1, 2, 4 and so on. Your task is to find the nth tribonacci number.

INPUT

First line of input contains t , the number of test cases. The next t lines contains an integers n, denoting the nth tribonacci number.

OUTPUT

Print the nth tribonacci number.

CONSTRAINTS

$1 \leq t \leq 20$

$1 \leq n \leq 30$