Problem Description

原始人总教头创建了自己的超绝题单，为了考验你能否参与进这场集训，你需要解读一串总教头提供的原始符号。 符号由a个n个正整数组成的数组。你可以在字符中选择任意两个相邻且不相等的数字，把他们合并成它们的和。具体来说，选一个下标 i ,满足1<=i<n和ai≠ai+1不相等，然后把ai和a(i+1)从数组中删掉，替换成它们的和ai+a(i+1). 举个例子，【9，5，4，9】中你可以选择i=2，操作后数组变成【9，9，9】。但由于新数组每一个数字都相同，就不能再重复之前的操作了。 我们可以发现，每一次操作，符号长度会减少1。那么，经过若干次操作，密码最短能缩到多长？

Input Format

输入包含多组测试数据。第一行是测试组数 t（1≤t≤100）。接下来是每组测试数据的描述。

每组测试数据第一行是一个整数 n（1≤n≤2⋅10^5）——密码的长度。

第二行是n个整数a1,a2,…,an（1≤ai≤10^9）——密码的初始内容。

所有测试组的 n 之和不超过 2⋅10^5。

Output Format

对于每组密码，输出一个整数：经过若干次操作后密码可能达到的最短长度。

2
4
2 1 3 1
2
420 420

1
2