Taco Journey

You are given a journey consisting of N segments. At each step, a traveler can move forward by 1, 2, or 3 segments. Although an array of segments is provided, its values do not affect the computation. Your task is to determine the number of distinct ways to complete the journey by traversing all segments.

The number of ways can be computed using the recurrence relation: $$dp[i] = dp[i-1] + dp[i-2] + dp[i-3]$$ with the base condition $$dp[0]=1$$.

Example:
For N = 4 (segments can be thought of as positions), the valid ways to jump are: (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1), amounting to 7 distinct ways.

inputFormat

The first line of input contains an integer T, the number of test cases. Each test case consists of two lines. The first line contains a single integer N representing the number of segments. The second line contains N space-separated integers (which may be ignored) representing the segments.

outputFormat

For each test case, output a single integer on a new line representing the number of ways to complete the journey.## sample

2
4
0 0 1 -1
3
0 1 1

7
4