Stripe#1537
Sign in

Stripe

1 second
128 megabytes
Very easy

A rectangle of size 1 \times n is given, divided into 1 \times 1 cells. Each cell can be colored either white or black.

The code of this rectangle is defined as a sequence of numbers, each of which is equal to the number of consecutive black cells when the rectangle is viewed from left to right.

For example, the code of the rectangle shown above is . The number of white cells is not taken into account; moreover, each group of black cells must be separated from the next one by at least one white cell. Therefore, the same code may correspond to several different rectangles. In particular, the following rectangle also has the given code:

Determine the number of rectangles that correspond to the given code.

Input

The first line contains the number of test cases t~(1 < t < 20). Each of the following lines describes one test case and contains:

  • the length of the rectangle n~(1 \le n \le 200);

  • the number of elements in the code k~(0 \le k \le \frac{n+1}{2});

  • integers describing the code.

Output

For each test case, print in a separate line the number of rectangles that correspond to the given code.

Examples

Example 1

Loading
Loading