Roy has played a lot of Mario that he got bored of playing it again and again. So now he wants to design a stage of Mario game.

Right now he is simply designing a group of walls using bricks that little Mario has to cross over. Little Mario cannot jump more than 3 bricks' height, so Roy cannot create a wall of height more than 3.

Roy has N number of bricks. Roy wants to make a group of walls such that height of no single wall exceeds 3.

For example if N = 8, one of the group of walls can be as follows:

Now Roy wonders how many different groups of walls can he generate for a given number of bricks.
(See Sample Test Case Explanation for clarification)

Input:
First line contains integer T, number of Test Cases. 
Next T lines each will contain integer N, number of bricks Roy has.

Output:
Print an integer in new line for each test case, number of different groups of walls.

Since answer can be very large, print it modulo 1000000007

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 100000

Sample Test Case Explanation:  For N = 3SAMPLE INPUT
1
3

SAMPLE OUTPUT
4
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

a = [0]*100015
MOD = 1000000007
def foo():
	a[0]=0;
	a[1]=1;
	a[2]=2;
	a[3]=4;
	for i in range (4,100010):
		a[i] = a[i-1]+a[i-2]+a[i-3]
		a[i] = a[i] % MOD
	

foo()
_ = input();

for __ in range(_):
	n = input()
	print a[n]