#include <bits/stdc++.h>
using namespace std;
const long long fix = (long long)1e9 + 7;
long long po2(long long a) {
  double temp = a;
  if (log2(temp) == (long long)log2(temp)) return log2(temp);
  return -1;
}
void tc(long long i) { cout << "Case #" << i + 1 << ": "; }
void yes() { cout << "YES" << '\n'; }
void no() { cout << "NO" << '\n'; }
void impb() { cout << "IMPOSSIBLE" << '\n'; }
long long ct() {
  long long t;
  scanf("%lld", &t);
  return t;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long pwr(long long a, long long b) {
  long long x = 1, y = a;
  while (b > 0) {
    if (b % 2) x = (x * y) % fix;
    y = (y * y) % fix;
    b /= 2;
  }
  return x;
}
long long pmodinv(long long a) { return pwr(a, fix - 2); }
vector<vector<long long> > adj;
const long long N = 1e5 + 5;
bool visited[N] = {};
queue<long long> q;
long long comanc(long long u, long long v, long long parent[]) {
  while (u ^ v) {
    if (u == 1 || v == 1) return 1;
    u = parent[u];
    v = parent[v];
  }
  return u;
}
long long x;
long long max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
vector<long long> factorial((long long)4002);
long long nCr(long long n, long long k) {
  return (factorial[n] *
          ((pmodinv(factorial[k]) * pmodinv(factorial[n - k])) % fix)) %
         fix;
}
long long dsu_par[N];
long long sze[N];
void make_set(long long n) {
  for (long long j = (1); j < (n + 1); j++) {
    dsu_par[j] = j;
    sze[j] = 1;
  }
}
long long find_set(long long a) {
  if (dsu_par[a] == a) return a;
  return dsu_par[a] = find_set(dsu_par[a]);
}
void union_set(long long a, long long b) {
  a = find_set(a);
  b = find_set(b);
  if (a ^ b) {
    if (sze[a] < sze[b]) swap(a, b);
    dsu_par[b] = a;
    sze[a] += sze[b];
  }
}
map<pair<long long, long long>, long long> mp;
vector<vector<long long> > up;
vector<long long> tin, tout;
long long dfs_timer = 0;
long long lim;
long long dist[N] = {};
void _dfs(long long v, long long par) {
  tin[v] = ++dfs_timer;
  up[v][0] = par;
  for (long long j = (1); j < (lim + 1); j++)
    up[v][j] = up[up[v][j - 1]][j - 1];
  for (long long u : adj[v]) {
    if (u ^ par) {
      dist[u] = dist[v] + mp.find(pair<long long, long long>(u, v))->second;
      _dfs(u, v);
    }
  }
  tout[v] = ++dfs_timer;
}
bool is_anc(long long u, long long v) {
  return tin[u] <= tin[v] && tout[u] >= tout[v];
}
long long lca(long long u, long long v) {
  if (is_anc(u, v)) return u;
  if (is_anc(v, u)) return v;
  for (long long i = lim; i >= 0; i--)
    if (is_anc(up[u][i], v) ^ 1) u = up[u][i];
  return up[u][0];
}
long long min(long long a, long long b) {
  if (a < b) return a;
  return b;
}
long long bisearch(vector<pair<long long, long long> >& operate,
                   long long limit) {
  long long lo = 0, hi = operate.size() - 1;
  while (lo < hi) {
    long long mid = lo + (hi - lo + 1) / 2;
    if (operate[mid].first > limit)
      hi = mid - 1;
    else
      lo = mid;
  }
  return lo;
}
int32_t main() {
  long long t = 1;
  t = ct();
  for (long long ii = (0); ii < (t); ii++) {
    long long n = ct();
    long long arr[n];
    for (long long j = (0); j < (n); j++) {
      cin >> arr[j];
    }
    long long cnt = 1;
    for (long long j = (1); j < (n); j++) {
      if (arr[j] == arr[0]) cnt++;
    }
    if (cnt == n)
      cout << n << '\n';
    else
      cout << "1" << '\n';
  }
}

### Prompt

Generate a Cpp solution to the following problem:

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 ≤ i < n and a_{i} ≠ 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 ≤ t ≤ 100). Description of the test cases follows.

The first line of each test case contains an integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of the password.

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

The sum of n over all test cases will not exceed 2 ⋅ 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long fix = (long long)1e9 + 7;
long long po2(long long a) {
  double temp = a;
  if (log2(temp) == (long long)log2(temp)) return log2(temp);
  return -1;
}
void tc(long long i) { cout << "Case #" << i + 1 << ": "; }
void yes() { cout << "YES" << '\n'; }
void no() { cout << "NO" << '\n'; }
void impb() { cout << "IMPOSSIBLE" << '\n'; }
long long ct() {
  long long t;
  scanf("%lld", &t);
  return t;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long pwr(long long a, long long b) {
  long long x = 1, y = a;
  while (b > 0) {
    if (b % 2) x = (x * y) % fix;
    y = (y * y) % fix;
    b /= 2;
  }
  return x;
}
long long pmodinv(long long a) { return pwr(a, fix - 2); }
vector<vector<long long> > adj;
const long long N = 1e5 + 5;
bool visited[N] = {};
queue<long long> q;
long long comanc(long long u, long long v, long long parent[]) {
  while (u ^ v) {
    if (u == 1 || v == 1) return 1;
    u = parent[u];
    v = parent[v];
  }
  return u;
}
long long x;
long long max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
vector<long long> factorial((long long)4002);
long long nCr(long long n, long long k) {
  return (factorial[n] *
          ((pmodinv(factorial[k]) * pmodinv(factorial[n - k])) % fix)) %
         fix;
}
long long dsu_par[N];
long long sze[N];
void make_set(long long n) {
  for (long long j = (1); j < (n + 1); j++) {
    dsu_par[j] = j;
    sze[j] = 1;
  }
}
long long find_set(long long a) {
  if (dsu_par[a] == a) return a;
  return dsu_par[a] = find_set(dsu_par[a]);
}
void union_set(long long a, long long b) {
  a = find_set(a);
  b = find_set(b);
  if (a ^ b) {
    if (sze[a] < sze[b]) swap(a, b);
    dsu_par[b] = a;
    sze[a] += sze[b];
  }
}
map<pair<long long, long long>, long long> mp;
vector<vector<long long> > up;
vector<long long> tin, tout;
long long dfs_timer = 0;
long long lim;
long long dist[N] = {};
void _dfs(long long v, long long par) {
  tin[v] = ++dfs_timer;
  up[v][0] = par;
  for (long long j = (1); j < (lim + 1); j++)
    up[v][j] = up[up[v][j - 1]][j - 1];
  for (long long u : adj[v]) {
    if (u ^ par) {
      dist[u] = dist[v] + mp.find(pair<long long, long long>(u, v))->second;
      _dfs(u, v);
    }
  }
  tout[v] = ++dfs_timer;
}
bool is_anc(long long u, long long v) {
  return tin[u] <= tin[v] && tout[u] >= tout[v];
}
long long lca(long long u, long long v) {
  if (is_anc(u, v)) return u;
  if (is_anc(v, u)) return v;
  for (long long i = lim; i >= 0; i--)
    if (is_anc(up[u][i], v) ^ 1) u = up[u][i];
  return up[u][0];
}
long long min(long long a, long long b) {
  if (a < b) return a;
  return b;
}
long long bisearch(vector<pair<long long, long long> >& operate,
                   long long limit) {
  long long lo = 0, hi = operate.size() - 1;
  while (lo < hi) {
    long long mid = lo + (hi - lo + 1) / 2;
    if (operate[mid].first > limit)
      hi = mid - 1;
    else
      lo = mid;
  }
  return lo;
}
int32_t main() {
  long long t = 1;
  t = ct();
  for (long long ii = (0); ii < (t); ii++) {
    long long n = ct();
    long long arr[n];
    for (long long j = (0); j < (n); j++) {
      cin >> arr[j];
    }
    long long cnt = 1;
    for (long long j = (1); j < (n); j++) {
      if (arr[j] == arr[0]) cnt++;
    }
    if (cnt == n)
      cout << n << '\n';
    else
      cout << "1" << '\n';
  }
}

```