You are given a rectangle 1 × n, where its 1 × 1 squares can be painted as white or black. So, one can build a "code" of this rectangle - this will be a sequence of numbers, the number of consequent black squares from left to right.

For example, the code of this rectangle is 2 3 2 8 1. However, the number of white squares is not counted anywhere (but two groups of black squares must be separated by at least one white square). That is why, there are a few rectangles which can satisfy the same code. For example, the following rectangle satisfies the given code as well.

The problem is to calculate the number of rectangles, which can satisfy the given code.

Input

There can be multiple test cases. The first line of the input gives you the number of test cases t (1 < t < 20). In the next t lines you would have the input for each of the test cases. Each test case consists of n (1 ≤ n ≤ 200) the length of a rectangle. Then k (0 ≤ k ≤ (n + 1) / 2) - the number of numbers in a code. Then k numbers, which represent the code itself.

Output

The output consists of one number - the number of rectangles, which can satisfy the given code. You can assume that the output will always fit in a 50 digit integer.