#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + "," +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug(T...);
}
struct Fast_power {
  long long integer(long long n, long long e,
                    long long my_mod = 9223372036854775807LL) {
    long long ans = 1;
    while (e) {
      if (e & 1)
        ans = (ans * n) % my_mod, e--;
      else
        n = (n * n) % my_mod, e >>= 1;
    }
    return ans;
  }
  vector<vector<long long>> matrix_multiply(vector<vector<long long>> a,
                                            vector<vector<long long>> b) {
    vector<vector<long long>> c(a.size(), vector<long long>(b[0].size(), 0));
    for (int i = 0; i < a.size(); i++)
      for (int q = 0; q < b[0].size(); q++) {
        long long num = 0;
        for (int e = 0; e < a[0].size(); i++) num += a[i][e] * b[e][q];
        c[i][q] = num;
      }
    return c;
  }
};
struct Euclidean {
  int gcdi(int a, int b) { return b ? gcdi(b, a % b) : a; }
  double gcdf(double a, double b, double accuracy) {
    return b <= accuracy ? a : gcdf(b, fmod(a, b), accuracy);
  }
};
const int maxnD = 100000 + 5;
const long long INFD = 0x3f3f3f3f;
;
struct Dijkstra {
  struct Edge {
    int from, to;
    long long dist;
  };
  struct HeapNode {
    long long d;
    int u;
    bool operator<(const HeapNode &rhs) const { return d > rhs.d; }
  };
  vector<Edge> edges;
  vector<int> G[maxnD];
  bool done[maxnD];
  long long d[maxnD];
  int p[maxnD], n;
  void init(int n) {
    this->n = n;
    for (int i = 0; i <= n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, long long dist) {
    edges.push_back((Edge){from, to, dist});
    int m = edges.size();
    G[from].push_back(m - 1);
  }
  void dijkstra(int s) {
    priority_queue<HeapNode> q;
    memset(d, INFD, sizeof(d));
    d[s] = 0;
    memset(done, 0, sizeof(done));
    q.push((HeapNode){0, s});
    while (!q.empty()) {
      HeapNode x = q.top();
      q.pop();
      int u = x.u;
      if (done[u]) continue;
      done[u] = true;
      for (int i = 0; i < G[u].size(); i++) {
        Edge &e = edges[G[u][i]];
        if (d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          q.push((HeapNode){d[e.to], e.to});
        }
      }
    }
  }
};
const int maxnL = 500000 + 5;
const int INFL = 0x3f3f3f3f;
struct LIS {
  int g[maxnL], a[maxnL], d[maxnL];
  void lis(int n) {
    for (int i = 1; i <= n; i++) g[i] = INFL;
    for (int i = 1; i < n; i++) {
      int k = lower_bound(g + 1, g + n + 1, a[i]) - g;
      g[k] = a[i];
    }
  }
};
const int maxnS = 200000 + 5;
struct SegmentTree {
  int a[maxnS];
  int sumv[maxnS * 4], minv[maxnS * 4], maxv[maxnS * 4], addv[maxnS * 4],
      setv[maxnS * 4];
  int lc, rc, v;
  int _min, _max, _sum;
  void build(int l, int r, int o) {
    if (l == r) return void(sumv[o] = minv[o] = maxv[o] = a[l]);
    build(l, (l + r) >> 1, o << 1);
    build(((l + r) >> 1) + 1, r, o << 1 | 1);
  }
  void maintain(int l, int r, int o) {
    sumv[o] = minv[o] = maxv[o] = a[l];
    if (r > l) {
      sumv[o] = sumv[o << 1] + sumv[o << 1 | 1];
      minv[o] = min(minv[o << 1], minv[o << 1 | 1]);
      maxv[o] = max(maxv[o << 1], maxv[o << 1 | 1]);
    }
    minv[o] += addv[o], maxv[o] += addv[o], sumv[o] += addv[o] * (r - l + 1);
  }
  void update(int l, int r, int o) {
    if (l >= lc && r <= rc)
      addv[o] += v;
    else {
      int m = (l + r) >> 1;
      if (lc <= m) update(l, (l + r) >> 1, o << 1);
      if (rc > m) update(((l + r) >> 1) + 1, r, o << 1 | 1);
    }
    maintain(l, r, o);
  }
  void query(int l, int r, int o, int add) {
    if (lc <= l && r <= rc) {
      _sum += sumv[o] + add * (r - l + 1);
      _min = min(_min, minv[o] + add);
      _max = max(_max, maxv[o] + add);
    } else {
      int m = (l + r) >> 1;
      if (lc <= m) query(l, m, o << 1, add + addv[o]);
      if (rc > m) query(m + 1, r, o << 1 | 1, add + addv[o]);
    }
  }
};
const int maxnB = 100000 + 5;
struct BIT {
  int c[maxnB], n;
  int lowbit(int x) { return x & -x; }
  int sum(int x) {
    int ret = 0;
    while (x > 0) {
      ret += c[x];
      x -= lowbit(x);
    }
    return ret;
  }
  void add(int x, int d) {
    while (x <= n) {
      c[x] += d;
      x += lowbit(x);
    }
  }
};
const int maxnEC = 200000 + 5;
struct EXCRT {
  long long ai[maxnEC], bi[maxnEC], n;
  inline long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (!b) {
      x = 1, y = 0;
      return a;
    }
    long long gcd = exgcd(b, a % b, x, y);
    long long t = x;
    x = y, y = t - (a / b) * y;
    return gcd;
  }
  inline long long mul(long long a, long long b, long long mod) {
    long long s = 0;
    while (b) {
      if (b & 1) s = (s + a) % mod;
      a = (a + a) % mod;
      b >>= 1;
    }
    return s % mod;
  }
  long long excrt() {
    long long x = 0, y = 0, k;
    long long M = bi[1], ans = ai[1];
    for (int i = 2; i <= 2; i++) {
      long long a = M, b = bi[i], c = (ai[i] - ans % b + b) % b;
      long long gcd = exgcd(a, b, x, y), bg = b / gcd;
      if (c % gcd != 0) return -1;
      x = mul(x, c / gcd, bg);
      ans += x * M;
      M *= bg;
      ans = (ans % M + M) % M;
    }
    return (ans % M + M) % M;
  }
};
const int INF = 0x3f3f3f3f;
const int maxn = 100000 + 5;
signed main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    int f1, ok = 1;
    cin >> f1;
    int f2;
    for (int i = 1; i < n; i++) {
      cin >> f2;
      if (f1 != f2) ok = 0;
    }
    if (ok)
      cout << n << endl;
    else
      cout << 1 << endl;
  }
  return 0;
}

### Prompt

Please formulate 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;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + "," +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug(T...);
}
struct Fast_power {
  long long integer(long long n, long long e,
                    long long my_mod = 9223372036854775807LL) {
    long long ans = 1;
    while (e) {
      if (e & 1)
        ans = (ans * n) % my_mod, e--;
      else
        n = (n * n) % my_mod, e >>= 1;
    }
    return ans;
  }
  vector<vector<long long>> matrix_multiply(vector<vector<long long>> a,
                                            vector<vector<long long>> b) {
    vector<vector<long long>> c(a.size(), vector<long long>(b[0].size(), 0));
    for (int i = 0; i < a.size(); i++)
      for (int q = 0; q < b[0].size(); q++) {
        long long num = 0;
        for (int e = 0; e < a[0].size(); i++) num += a[i][e] * b[e][q];
        c[i][q] = num;
      }
    return c;
  }
};
struct Euclidean {
  int gcdi(int a, int b) { return b ? gcdi(b, a % b) : a; }
  double gcdf(double a, double b, double accuracy) {
    return b <= accuracy ? a : gcdf(b, fmod(a, b), accuracy);
  }
};
const int maxnD = 100000 + 5;
const long long INFD = 0x3f3f3f3f;
;
struct Dijkstra {
  struct Edge {
    int from, to;
    long long dist;
  };
  struct HeapNode {
    long long d;
    int u;
    bool operator<(const HeapNode &rhs) const { return d > rhs.d; }
  };
  vector<Edge> edges;
  vector<int> G[maxnD];
  bool done[maxnD];
  long long d[maxnD];
  int p[maxnD], n;
  void init(int n) {
    this->n = n;
    for (int i = 0; i <= n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, long long dist) {
    edges.push_back((Edge){from, to, dist});
    int m = edges.size();
    G[from].push_back(m - 1);
  }
  void dijkstra(int s) {
    priority_queue<HeapNode> q;
    memset(d, INFD, sizeof(d));
    d[s] = 0;
    memset(done, 0, sizeof(done));
    q.push((HeapNode){0, s});
    while (!q.empty()) {
      HeapNode x = q.top();
      q.pop();
      int u = x.u;
      if (done[u]) continue;
      done[u] = true;
      for (int i = 0; i < G[u].size(); i++) {
        Edge &e = edges[G[u][i]];
        if (d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          q.push((HeapNode){d[e.to], e.to});
        }
      }
    }
  }
};
const int maxnL = 500000 + 5;
const int INFL = 0x3f3f3f3f;
struct LIS {
  int g[maxnL], a[maxnL], d[maxnL];
  void lis(int n) {
    for (int i = 1; i <= n; i++) g[i] = INFL;
    for (int i = 1; i < n; i++) {
      int k = lower_bound(g + 1, g + n + 1, a[i]) - g;
      g[k] = a[i];
    }
  }
};
const int maxnS = 200000 + 5;
struct SegmentTree {
  int a[maxnS];
  int sumv[maxnS * 4], minv[maxnS * 4], maxv[maxnS * 4], addv[maxnS * 4],
      setv[maxnS * 4];
  int lc, rc, v;
  int _min, _max, _sum;
  void build(int l, int r, int o) {
    if (l == r) return void(sumv[o] = minv[o] = maxv[o] = a[l]);
    build(l, (l + r) >> 1, o << 1);
    build(((l + r) >> 1) + 1, r, o << 1 | 1);
  }
  void maintain(int l, int r, int o) {
    sumv[o] = minv[o] = maxv[o] = a[l];
    if (r > l) {
      sumv[o] = sumv[o << 1] + sumv[o << 1 | 1];
      minv[o] = min(minv[o << 1], minv[o << 1 | 1]);
      maxv[o] = max(maxv[o << 1], maxv[o << 1 | 1]);
    }
    minv[o] += addv[o], maxv[o] += addv[o], sumv[o] += addv[o] * (r - l + 1);
  }
  void update(int l, int r, int o) {
    if (l >= lc && r <= rc)
      addv[o] += v;
    else {
      int m = (l + r) >> 1;
      if (lc <= m) update(l, (l + r) >> 1, o << 1);
      if (rc > m) update(((l + r) >> 1) + 1, r, o << 1 | 1);
    }
    maintain(l, r, o);
  }
  void query(int l, int r, int o, int add) {
    if (lc <= l && r <= rc) {
      _sum += sumv[o] + add * (r - l + 1);
      _min = min(_min, minv[o] + add);
      _max = max(_max, maxv[o] + add);
    } else {
      int m = (l + r) >> 1;
      if (lc <= m) query(l, m, o << 1, add + addv[o]);
      if (rc > m) query(m + 1, r, o << 1 | 1, add + addv[o]);
    }
  }
};
const int maxnB = 100000 + 5;
struct BIT {
  int c[maxnB], n;
  int lowbit(int x) { return x & -x; }
  int sum(int x) {
    int ret = 0;
    while (x > 0) {
      ret += c[x];
      x -= lowbit(x);
    }
    return ret;
  }
  void add(int x, int d) {
    while (x <= n) {
      c[x] += d;
      x += lowbit(x);
    }
  }
};
const int maxnEC = 200000 + 5;
struct EXCRT {
  long long ai[maxnEC], bi[maxnEC], n;
  inline long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (!b) {
      x = 1, y = 0;
      return a;
    }
    long long gcd = exgcd(b, a % b, x, y);
    long long t = x;
    x = y, y = t - (a / b) * y;
    return gcd;
  }
  inline long long mul(long long a, long long b, long long mod) {
    long long s = 0;
    while (b) {
      if (b & 1) s = (s + a) % mod;
      a = (a + a) % mod;
      b >>= 1;
    }
    return s % mod;
  }
  long long excrt() {
    long long x = 0, y = 0, k;
    long long M = bi[1], ans = ai[1];
    for (int i = 2; i <= 2; i++) {
      long long a = M, b = bi[i], c = (ai[i] - ans % b + b) % b;
      long long gcd = exgcd(a, b, x, y), bg = b / gcd;
      if (c % gcd != 0) return -1;
      x = mul(x, c / gcd, bg);
      ans += x * M;
      M *= bg;
      ans = (ans % M + M) % M;
    }
    return (ans % M + M) % M;
  }
};
const int INF = 0x3f3f3f3f;
const int maxn = 100000 + 5;
signed main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    int f1, ok = 1;
    cin >> f1;
    int f2;
    for (int i = 1; i < n; i++) {
      cin >> f2;
      if (f1 != f2) ok = 0;
    }
    if (ok)
      cout << n << endl;
    else
      cout << 1 << endl;
  }
  return 0;
}

```