题目描述

Omkar 大人允许你进入 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 \leq t \leq 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$：

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

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

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

在第二个测试用例中，你无法进行任何操作，因为没有满足条件的 $i$。

由 ChatGPT 4.1 翻译

样例

2
4
2 1 3 1
2
420 420

1
2