Є прямокутник розміром 1 × n, квадрати 1×1 якого можна зафарбувати білим чи чорним кольором. За прямокутником можна побудувати "код" - послідовність чисел, рівних кількості чорних квадратів, що йдуть поспіль зліва направо.

Наприклад, код цього прямокутника 2 3 2 8 1. Але кількість білих квадратів ніде не враховується (групи чорних клітин повинні розділятися як мінімум однією білою клітиною). Тому одному і тому ж коду може відповідати декілька прямокутників. Наприклад, вище наведеному коду також відповідає прямокутник

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

Вхідні дані

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

Вихідні дані

Для кожного тесту вивести в окремому рядку одне число - кількість прямокутників, що задовольняють заданому коду. Відповідь завжди буде не більшою за 50 знакове ціле.