Задача #0169

Мирзо Улугбек пошел в книжный магазин за книгами. К сожалению, в кошельке не хватило денег ни на какие книги. Видя интерес Мирзо Улугбека к книгам, хозяин библиотеки, наблюдавший со стороны, пригласил Мирзо Улугбека поиграть в игру, чтобы подарить ему книгу. Хозяйн магазина сказал, что подарит столько книг, сколько Мирзо Улугбек наберет очков в игре. Естественно, Мирзо Улугбек согласился и внимательно выслушал условия игры:

- Мирзо Улугбеку дан массив неотрицательных целых чисел.

- Мирзо Улугбек должен разделить массив на 2 непустых массива, состоящих из последовательных элементов, так, чтобы сумма элементов массива, состоящего из элементов слева, была равна сумме элементов массива, состоящего из элементов справа. необходимость Если Мирзо Улугбек сможет это сделать, он получит 1 очко, иначе игра закончится.

- После каждого успешного раунда Мирзо Улугбек выбрасывает массив левых или правых элементов и продолжает игру с оставшимся массивом.

Например: сначала Мирзо Улугбек имеет массив \([1,2,3,6]\), он может разделить этот массив на две части \([1,2,3,6]\), \([6]\) (+1 балл), затем \([6]\) удаляется из игры, и игра продолжается с \([1,2,3]\). Он может разбить этот массив на две части \([1,2]\), \([3]\) (+1 балл), затем удалить \([3]\) из игры и продолжить игру с \([1,2]\). Он не может разделить массив пополам, и к концу игры у Мирзо Улугбека будет 2 очка, а это значит, что он может бесплатно взять любые 2 книги из книжного магазина.

В первой строке дано одно целое число \(T (1 ≤ T ≤ 10)\) - количество тестов. Начиная со следующей строки, \(N (1 ≤ N ≤ 2^{14})\) в первой строке из двух отдельных строк для каждого теста - количество элементов массива, во второй строке - \(N\) целых чисел в диапазоне \([0, 10^9]\), т.е. у Мирзо Улугбека вводятся начальные элементы массива.

Выведите целое число в отдельной строке для каждого теста, сколько книг Мирзо Улугбек взял бы в книжном магазине бесплатно.