NIKITHA AND THE GAME

PROBLEM STATEMENT:

Nikita just came up with a new array game. The rules are as follows:

• Initially, there is an array, A$A$, containing N$N$ integers.
• In each move, Nikita must partition the array into 2$2$ non-empty parts such that the sum of the elements in the left partition is equal to the sum of the elements in the right partition. If Nikita can make such a move, she gets 1$1$ point; otherwise, the game ends.
• After each successful move, Nikita discards either the left partition or the right partition and continues playing by using the remaining partition as array A$A$.

Nikita loves this game and wants your help getting the best score possible. Given A$A$, can you find and print the maximum number of points she can score?

Input Format

The first line contains an integer, T$T$, denoting the number of test cases. Each test case is described over 2$2$ lines in the following format:

1. A line containing a single integer, N$N$, denoting the size of array A$A$.
2. A line of N$N$ space-separated integers describing the elements in array A$A$.

Constraints

• 1≤T≤10$1\le T\le 10$
• 1≤N≤214$1\le N\le 2^{14}$
• 0≤Ai≤109$0\le A_i\le {10}^9$

Scoring

• 1≤N≤28$1\le N\le 2^8$ for 30%$30\mathrm{\%}$ of the test data
• 1≤N≤211$1\le N\le 2^{11}$ for 60%$60\mathrm{\%}$ of the test data
• 1≤N≤214$1\le N\le 2^{14}$ for 100%$100\mathrm{\%}$ of the test data

Output Format

For each test case, print Nikita's maximum possible score on a new line.

PYTHON CODE: 
T = input()

while T > 0:
    N = input()
    A = map(int, raw_input().strip().split(' '))

    score = 0

    fsum = A*1
    h = {fsum[0]:0}
    for i in xrange(1,N):
        fsum[i] += fsum[i-1]
        h[fsum[i]] = i
    anchors = {0:True}      # half-points in sum-space

    if fsum[-1]==0:         # if all zeros
        score = N-1
    elif fsum[-1]%2==0:
        offset = fsum[-1]/2
        while anchors:
            for a in anchors.keys():
                if (a+offset) in h:
                    anchors[a+offset] = True
                else:
                    del anchors[a]
            if anchors:     # some offsets succeeded
                score += 1
            if offset%2==0:
                offset /= 2
            else:
                anchors = None

    print score

    T -= 1
OUTPUT: