Степан любить задачі з масивами. На жаль, останню, яку він намагався вирішити, не вдалося нормально написати.

Степан має масив \(A\) з \(N\) додатних чисел. Він хоче знайти кількість підмасивів, для яких сума і добуток елементів рівні.

Будь ласка, допоможіть Степану знайти це число.

Формат вхідних даних

Перший рядок містить ціле число \(T\) - кількість тестів.

Перший рядок тесту містить \(N\)

Наступний рядок тесту містить \(N\) цілих чисел \(A_i\)

Формат вихідних даних

У вихідний потік вивести, в окремих рядках для кожного тесту, відповідь на поставлене завдання

Обмеження

• 1 ≤ T ≤ 50

• 1 ≤ N ≤ 50

• \(1 ≤ A_i ≤ 10^9\)

• \(A_1 * A_2 * ... * A_N ≤ 10^9\)

Приклад вхідних даних

3
3
1 3 2
4
4 1 2 1
6
1 2 2 2 2 1

Приклад вихідних даних

4
5
9