Petya and Vasya are playing a game. Petya's got *n* non-transparent glasses, standing in a row. The glasses' positions are indexed with integers from 1 to *n* from left to right. Note that the positions are indexed but the glasses are not.

First Petya puts a marble under the glass in position *s*. Then he performs some (possibly zero) shuffling operations. One shuffling operation means moving the glass from the first position to position *p*<sub class="lower-index">1</sub>, the glass from the second position to position *p*<sub class="lower-index">2</sub> and so on. That is, a glass goes from position *i* to position *p*<sub class="lower-index">*i*</sub>. Consider all glasses are moving simultaneously during one shuffling operation. When the glasses are shuffled, the marble doesn't travel from one glass to another: it moves together with the glass it was initially been put in.

After all shuffling operations Petya shows Vasya that the ball has moved to position *t*. Vasya's task is to say what minimum number of shuffling operations Petya has performed or determine that Petya has made a mistake and the marble could not have got from position *s* to position *t*.
The first line contains three integers: *n*, *s*, *t* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>; 1 ≤ *s*, *t* ≤ *n*) — the number of glasses, the ball's initial and final position. The second line contains *n* space-separated integers: *p*<sub class="lower-index">1</sub>, *p*<sub class="lower-index">2</sub>, ..., *p*<sub class="lower-index">*n*</sub> (1 ≤ *p*<sub class="lower-index">*i*</sub> ≤ *n*) — the shuffling operation parameters. It is guaranteed that all *p*<sub class="lower-index">*i*</sub>'s are distinct.

Note that *s* can equal *t*.
import sys
from os import path
from collections import deque, Counter, defaultdict
from heapq import heappush, heappop, nlargest, nsmallest
import itertools
import math
from fractions import Fraction
import functools
    
debug = False
    
def debugprint(*args):
    if (debug):
        print('DEBUG:',*args)
    
def listToInteger(list):
    # Converting integer list to string list
    s = [str(i) for i in list]
    # Join list items using join()
    res = int("".join(s))
        
    return(res)
    
def lcm(*args):
    return functools.reduce(lambda a,b: (a*b) // math.gcd(a,b),[*args])
    
def gcd(*args):
    return functools.reduce(math.gcd,[*args])
    
def input():
    return sys.stdin.readline().strip()
    
def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        acc = set(itertools.accumulate(a))
        total = max(acc)

        ans = n
        debugprint(acc)

        # attempt all identical
        identical = True
        for i in range(1, n):
            if (a[i] != a[0]):
                identical = False
                break
        if (identical):
            print(1)
            continue

        # attempt 2split
        current = 0
        for i in range(n-1):
            current += a[i]

            if (current == total-current):
                ans = max(i+1, (n-i)-1)
                break
            if (current > total-current):
                break

        # attempt 3split
        debugprint(a)
        current = 0
        for i in range(1, n):
            for j in range(i+1, n):
                debugprint(sum(a[:i]), sum(a[i:j]), sum(a[j:]))
                if (sum(a[:i]) == sum(a[i:j]) and sum(a[:i]) == sum(a[j:])):
                    debugprint('a', i, j-i, n-j)
                    ans = min(ans, max(i, j-i, n-j))

        print(ans)

        # attempt divisors... idk
        for i in range(1,n):
            diviseurs = get_diviseurs(total, i)
            debugprint(diviseurs)
            if (diviseurs is not None):
                all_included = True
                length = None
                for j in range(len(diviseurs)):
                    if (diviseurs[j] not in acc):
                        print(diviseurs[j], acc)
                        all_included = False
                
                if (all_included):
                    debugprint('found')

def get_diviseurs(dividende, m):
    n = dividende // m

    if (n != (dividende/m)):
        return None
    else:
        return list(range(n, (m+1)*n, n))

    
if __name__ == "__main__":
    if(path.exists('input.txt')):
        debug = True
        sys.stdin = open("input.txt","r")
        # sys.stdout = open("output.txt","w")
    main()