B. Лунтик и подпоследовательности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лунтик вышел на утреннюю прогулку и нашел массив $$$a$$$ длины $$$n$$$. Он посчитал сумму $$$s$$$ элементов массива ($$$s= \sum_{i=1}^{n} a_i$$$). Лунтик называет подпоследовательность массива $$$a$$$ почти полной, если сумма чисел в этой подпоследовательности равна $$$s-1$$$.

Лунтик очень хочет узнать количество почти полных подпоследовательностей массива $$$a$$$. Но ему надо возвращаться домой, поэтому он просит вас решить эту задачу!

Напоминаем, что последовательность $$$x$$$ является подпоследовательностью $$$y$$$, если $$$x$$$ может быть получена из $$$y$$$ удалением нескольких (возможно, ни одного или всех) элементов.

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

В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Следующие $$$2 \cdot t$$$ строк содержат описания наборов входных данных. Описание каждого набора состоит из двух строк.

Первая строка описания каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 60$$$) — длину массива.

Во второй строке находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

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

Для каждого набора входных данных выведите количество почти полных подпоследовательностей массива.

Пример
Входные данные
5
5
1 2 3 4 5
2
1000 1000
2
1 0
5
3 0 2 1 1
5
2 1 0 3 0
Выходные данные
1
0
2
4
4
Примечание

В первом наборе входных данных $$$s=1+2+3+4+5=15$$$, из всех подпоследовательностей почти полной будет только $$$(2,3,4,5)$$$, сумма в ней равна $$$2+3+4+5=14=15-1$$$.

Во втором наборе входных данных нет почти полных подпоследовательностей.

В третьем наборе входных данных $$$s=1+0=1$$$, почти полными будут подпоследовательности $$$(0)$$$ и $$$()$$$ (пустая подпоследовательность имеет сумму $$$0$$$).