def f(x): if x==1 or x==2 or x==3: return x else: return 2*f(x-1)-f(x-2)+f(x-3) T=int(input()) for i in range(T): N=int(input()) a=f(N) print(a)