Lord Omkar has permitted you to enter the Holy Church of Omkar! To test your worthiness, Omkar gives you a password which you must interpret!

A password is an array $a$ of $n$ positive integers. You apply the following operation to the array: pick any two adjacent numbers that are not equal to each other and replace them with their sum. Formally, choose an index $i$ such that $1 \leq i < n$ and $a_{i} \neq a_{i+1}$, delete both $a_i$ and $a_{i+1}$ from the array and put $a_{i}+a_{i+1}$ in their place. 

For example, for array $[7, 4, 3, 7]$ you can choose $i = 2$ and the array will become $[7, 4+3, 7] = [7, 7, 7]$. Note that in this array you can't apply this operation anymore.

Notice that one operation will decrease the size of the password by $1$. What is the shortest possible length of the password after some number (possibly $0$) of operations?


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the password.

The second line of each test case contains $n$ integers $a_{1},a_{2},\dots,a_{n}$ ($1 \leq a_{i} \leq 10^9$) — the initial contents of your password.

The sum of $n$ over all test cases will not exceed $2 \cdot 10^5$.


-----Output-----

For each password, print one integer: the shortest possible length of the password after some number of operations.


-----Example-----
Input
2
4
2 1 3 1
2
420 420

Output
1
2



-----Note-----

In the first test case, you can do the following to achieve a length of $1$:

Pick $i=2$ to get $[2, 4, 1]$

Pick $i=1$ to get $[6, 1]$

Pick $i=1$ to get $[7]$

In the second test case, you can't perform any operations because there is no valid $i$ that satisfies the requirements mentioned above.

Difficulty: interview

Starter code:

Solutions:
# for _ in range(1):
for _ in range(int(input())):
    # a, b = map(int, input().split())
    n = int(input())
    arr = list(map(int, input().split()))
    # s = input()
    if [arr[0]] * n == arr:
        print(n)
    else:
        print(1)


import sys
import math
import itertools
import functools
import collections
import operator
import fileinput
import copy

ORDA = 97  # a
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return [int(i) for i in input().split()]
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def revn(n): return str(n)[::-1]
def dd(): return collections.defaultdict(int)
def ddl(): return collections.defaultdict(list)
def sieve(n):
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r
def divs(n, start=2):
    r = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if (n % i == 0):
            if (n / i == i):
                r.append(i)
            else:
                r.extend([i, n // i])
    return r
def divn(n, primes):
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t
def prime(n):
    if n == 2: return True
    if n % 2 == 0 or n <= 1: return False
    sqr = int(math.sqrt(n)) + 1
    for d in range(3, sqr, 2):
        if n % d == 0: return False
    return True
def convn(number, base):
    new_number = 0
    while number > 0:
        new_number += number % base
        number //= base
    return new_number
def cdiv(n, k): return n // k + (n % k != 0)
def ispal(s):
    for i in range(len(s) // 2 + 1):
        if s[i] != s[-i - 1]:
            return False
    return True


for _ in range(ii()):
    n = ii()
    a = li()
    if len(set(a)) == 1:
        print(n)
    else:
        print(1)

for _ in range(int(input())):
    N =int(input())
    List = [int(x) for x in input().split()]
    if(List.count(List[0]) == N):
        print(N)
    else:
        print(1)

t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(j) for j in input().split()]
	if arr.count(arr[0]) == n:
		print(n)
	else:
		print(1)

import sys
import math
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return list(map(int, sys.stdin.readline().split()))

def SI():
	return sys.stdin.readline().strip()
t = II()
for q in range(t):
	n = II()
	a = LI()
	print(1 if len(set(a)) != 1 else n)


import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    l = list(map(int, input().split()))
    if min(l) == max(l):
        print(n)
    else:
        print(1)


t = int(input())

for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    
    if len(set(a)) == 1:
        print(n)
    else:
        print(1)

def solve():
    kek = input()
    a = sorted(list(map(int, input().split())))
    if a[0] == a[-1]:
        print(len(a))
    else:
        print(1)


[solve() for x in range(int(input()))]


import sys

def input():    return sys.stdin.readline().strip()
def iinput():   return int(input())
def rinput():   return map(int, sys.stdin.readline().strip().split()) 
def get_list(): return list(map(int, sys.stdin.readline().strip().split())) 
mod = int(1e9)+7


for _ in range(iinput()):
	n = iinput()
	a = get_list()
	s = set(a)

	if (len(s)==1):
		print(n)
	else:
		print(1)	

for _ in range(int(input())):
    input()
    arr = list(map(int, input().split()))
    if len(set(arr)) == 1:
        print(len(arr))
    else:
        print(1)


#from collection import defaultdict as dd
import sys
input=sys.stdin.readline
t=int(input())
while t:
    n=int(input())
    #n,m=map(int,input().split())
    l=list(map(int,input().split()))
    s=set(l)
    if(len(s)==1):
        print(n)
    else:
        print(1)
    t-=1

import sys
input = sys.stdin.readline
for f in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    iseq=True
    for i in range(1,n):
        if a[i]!=a[i-1]:
            iseq=False
    if iseq:
        print(n)
    else:
        print(1)

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if len(set(a))==1:
        print(n)
    else:
        print(1)


inp = lambda cast=int: [cast(x) for x in input().split()]
printf = lambda s='', *args, **kwargs: print(str(s).format(*args), flush=True, **kwargs)

t, = inp()
for _ in range(t):
    n, = inp()
    print(n if len(set(inp())) == 1 else 1)

for i in range(int(input())):
    x = int(input())
    #n, m = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    if A[0] == A[-1]:
        print(len(A))
    else:
        print(1)

def solve():
    n = int(input())
    lst = list(map(int,input().split()))
    k = max(lst)
    lst2 = [i for i in lst if i != k]
    if len(lst2):
        print(1)
    else:
        print(n)
for i in range(int(input())):
    solve()

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    c = 0
    for i in a:
        if(i!=a[0]):
            c+=1
            break
    if(c!=0):
        print(1)
    else:
        print(n)

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int,input().split()))
    x = arr.count(arr[0])
    if x==n:
        print(n)
    else:
        print(1)

t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    same=1
    for i in range(n-1):
        if a[i]!=a[i+1]:
            same=0
            break
    if same==1:
        print(n)
    else:
        print(1)

import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    n=int(input())
    A=list(map(int,input().split()))

    if len(set(A))==1:
        print(n)
    else:
        print(1)