eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Полоса

Полоса

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Имеется прямоугольник размера 1 × n, квадратики 1 × 1 которого закрашены белым или черным цветом. По прямоугольнику можно построить "код" - последовательность чисел, равных количеству подряд идущих черных квадратов слева направо.

prb1537-1

Например, код этого прямоугольника 2 3 2 8 1. Однако количество белых квадратов нигде не учитывается (группы черных клеток должны разделяться как минимум одной белой клеткой). Поэтому одному и тому же коду может соответствовать несколько прямоугольников. Например, выше приведенному коду также соответствует прямоугольник

prb1537-2

Вам необходимо подсчитать количество прямоугольников, удовлетворяющих заданному коду.

Входные данные

Первая строка содержит количество тестов t (1 < t < 20). Каждая из следующих t строк содержит данные для одного теста. Каждый тест начинается длиной прямоугольника n (1n200). Затем идет k (0k ≤ (n + 1) / 2) - количество чисел в коде. Далее идут k чисел, описывающих непосредственно код.

Выходные данные

Для каждого теста вывести в отдельной строке одно число - количество прямоугольников, удовлетворяющих заданному коду. Ответ всегда помещается в 50 знаковое целое.

Пример

Входные данные #1
3
4 0
5 2 1 2
4 2 2 2
Выходные данные #1
1
3
0