#include <bits/stdc++.h>
using namespace std;
void abc() { cout << endl; }
template <typename T, typename... U>
void abc(T a, U... b) {
  cout << a << ' ', abc(b...);
}
template <typename T>
void printv(T l, T r) {
  while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B>
istream& operator>>(istream& o, pair<A, B>& a) {
  return o >> a.first >> a.second;
}
template <typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> a) {
  return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T>
ostream& operator<<(ostream& o, vector<T> a) {
  bool is = false;
  for (T i : a) {
    o << (is ? ' ' : '{'), is = true, o << i;
  }
  return o << '}';
}
template <typename T>
struct vv : vector<vector<T>> {
  vv(int n, int m, T v) : vector<vector<T>>(n, vector<T>(m, v)) {}
  vv() {}
};
template <typename T>
struct vvv : vector<vv<T>> {
  vvv(int n, int m, int k, T v) : vector<vv<T>>(n, vv<T>(m, k, v)) {}
  vvv() {}
};
const int mod = 998244353, N = 1000005, logC = 30, K = 450;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int ans = 1, pre, now;
    cin >> pre;
    if (pre) ans++;
    bool fail = false;
    for (int i = 1; i < n; ++i) {
      cin >> now;
      if (pre == 0 && now == 0) {
        fail = true;
      }
      if (pre == 1 && now == 1) ans += 5;
      if (pre == 0 && now == 1) ans++;
      pre = now;
    }
    if (fail) ans = -1;
    cout << ans << endl;
  }
}

### Prompt

Construct a Cpp code solution to the problem outlined:

Petya has got an interesting flower. Petya is a busy person, so he sometimes forgets to water it. You are given n days from Petya's live and you have to determine what happened with his flower in the end.

The flower grows as follows: 

  * If the flower isn't watered for two days in a row, it dies. 
  * If the flower is watered in the i-th day, it grows by 1 centimeter. 
  * If the flower is watered in the i-th and in the (i-1)-th day (i > 1), then it grows by 5 centimeters instead of 1. 
  * If the flower is not watered in the i-th day, it does not grow. 



At the beginning of the 1-st day the flower is 1 centimeter tall. What is its height after n days?

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 the only integer n (1 ≤ n ≤ 100).

The second line of each test case contains n integers a_1, a_2, ..., a_n (a_i = 0 or a_i = 1). If a_i = 1, the flower is watered in the i-th day, otherwise it is not watered.

Output

For each test case print a single integer k — the flower's height after n days, or -1, if the flower dies.

Example

Input


4
3
1 0 1
3
0 1 1
4
1 0 0 1
1
0


Output


3
7
-1
1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void abc() { cout << endl; }
template <typename T, typename... U>
void abc(T a, U... b) {
  cout << a << ' ', abc(b...);
}
template <typename T>
void printv(T l, T r) {
  while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B>
istream& operator>>(istream& o, pair<A, B>& a) {
  return o >> a.first >> a.second;
}
template <typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> a) {
  return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T>
ostream& operator<<(ostream& o, vector<T> a) {
  bool is = false;
  for (T i : a) {
    o << (is ? ' ' : '{'), is = true, o << i;
  }
  return o << '}';
}
template <typename T>
struct vv : vector<vector<T>> {
  vv(int n, int m, T v) : vector<vector<T>>(n, vector<T>(m, v)) {}
  vv() {}
};
template <typename T>
struct vvv : vector<vv<T>> {
  vvv(int n, int m, int k, T v) : vector<vv<T>>(n, vv<T>(m, k, v)) {}
  vvv() {}
};
const int mod = 998244353, N = 1000005, logC = 30, K = 450;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int ans = 1, pre, now;
    cin >> pre;
    if (pre) ans++;
    bool fail = false;
    for (int i = 1; i < n; ++i) {
      cin >> now;
      if (pre == 0 && now == 0) {
        fail = true;
      }
      if (pre == 1 && now == 1) ans += 5;
      if (pre == 0 && now == 1) ans++;
      pre = now;
    }
    if (fail) ans = -1;
    cout << ans << endl;
  }
}

```