← 返回题目列表

Codeforces · 1392/A

A. Omkar 和密码

中文机器翻译题面 查看原题

奥姆卡领主允许你进入奥姆卡圣教堂!为了测试你的价值,Omkar 给了你一个密码,你必须解读它!

密码是一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。您可以对数组应用以下操作:选取任意两个彼此不相等的相邻数字,并将它们替换为它们的总和。正式地,选择一个索引 $$$i$$$ 使得 $$$1 \leq i < n$$$ 和 $$$a_{i} \neq a_{i+1}$$$,从数组中删除 $$$a_i$$$ 和 $$$a_{i+1}$$$ 并将 $$$a_{i}+a_{i+1}$$$ 放在它们的位置。

例如,对于数组 $$$[7, 4, 3, 7]$$$,您可以选择 $$$i = 2$$$,数组将变为 $$$[7, 4+3, 7] = [7, 7, 7]$$$。请注意,在此数组中您无法再应用此操作。

请注意,一项操作会将密码大小减少 $$$1$$$。经过一定次数(可能是 $$$0$$$)操作后,密码的最短可能长度是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 密码的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$1 \leq a_{i} \leq 10^9$$$) - 密码的初始内容。

所有测试用例的 $$$n$$$ 总和不会超过 $$$2 \cdot 10^5$$$。

输出

对于每个密码,打印一个整数:经过一定次数的操作后密码的最短可能长度。

示例

输入 #1

2
4
2 1 3 1
2
420 420

输出 #1

1
2

注意

在第一个测试用例中,您可以执行以下操作来实现 $$$1$$$ 的长度:

选择 $$$i=2$$$ 得到 $$$[2, 4, 1]$$$

选择 $$$i=1$$$ 得到 $$$[6, 1]$$$

选择$$$i=1$$$ 得到$$$[7]$$$

在第二个测试用例中,您无法执行任何操作,因为没有满足上述要求的有效 $$$i$$$。