#include <bits/stdc++.h>
using namespace std;
vector<string> split(const string& s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
template <typename T, typename... Args>
inline string arrStr(T arr, long long n) {
  stringstream s;
  s << "[";
  for (long long i = 0; i < n - 1; i++) s << arr[i] << ",";
  s << arr[n - 1] << "]";
  return s.str();
}
template <typename t>
void evars(vector<vector<t>> a) {
  for (auto i : a) {
    for (auto j : i) {
      cout << j << " ";
    }
    cout << "\n";
  }
}
inline void __evars_begin(long long line) { cout << "#" << line << ": "; }
template <typename T>
inline void __evars_out_var(vector<T> val) {
  cout << arrStr(val, val.size());
}
template <typename T>
inline void __evars_out_var(T* val) {
  cout << arrStr(val, 10);
}
template <typename T>
inline void __evars_out_var(T val) {
  cout << val;
}
inline void __evars(vector<string>::iterator it) { cout << "\n"; }
template <typename T, typename... Args>
inline void __evars(vector<string>::iterator it, T a, Args... args) {
  cout << it->substr((*it)[0] == ' ', it->length()) << "=";
  __evars_out_var(a);
  cout << "; ";
  __evars(++it, args...);
}
void solve() {
  long long n;
  cin >> n;
  vector<long long> vals(n + 1);
  for (long long i = 1; i < n + 1; ++i) cin >> vals[i];
  vals[0] = 0;
  long long a = 0, b = 0;
  bool is_ok = true;
  for (long long i = 1; i < n + 1; ++i) {
    if (vals[i] && vals[i - 1]) {
      a++;
    } else if (vals[i] && !vals[i - 1]) {
      b++;
    } else if (!vals[i] && !vals[i - 1] && i != 1) {
      is_ok = false;
      break;
    }
  }
  (!is_ok) ? cout << -1 << "\n" : cout << (5 * a + b + 1) << "\n";
}
int32_t main() {
  clock_t begin = clock();
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  long long t;
  cin >> t;
  while (t--) solve();
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

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;
vector<string> split(const string& s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
template <typename T, typename... Args>
inline string arrStr(T arr, long long n) {
  stringstream s;
  s << "[";
  for (long long i = 0; i < n - 1; i++) s << arr[i] << ",";
  s << arr[n - 1] << "]";
  return s.str();
}
template <typename t>
void evars(vector<vector<t>> a) {
  for (auto i : a) {
    for (auto j : i) {
      cout << j << " ";
    }
    cout << "\n";
  }
}
inline void __evars_begin(long long line) { cout << "#" << line << ": "; }
template <typename T>
inline void __evars_out_var(vector<T> val) {
  cout << arrStr(val, val.size());
}
template <typename T>
inline void __evars_out_var(T* val) {
  cout << arrStr(val, 10);
}
template <typename T>
inline void __evars_out_var(T val) {
  cout << val;
}
inline void __evars(vector<string>::iterator it) { cout << "\n"; }
template <typename T, typename... Args>
inline void __evars(vector<string>::iterator it, T a, Args... args) {
  cout << it->substr((*it)[0] == ' ', it->length()) << "=";
  __evars_out_var(a);
  cout << "; ";
  __evars(++it, args...);
}
void solve() {
  long long n;
  cin >> n;
  vector<long long> vals(n + 1);
  for (long long i = 1; i < n + 1; ++i) cin >> vals[i];
  vals[0] = 0;
  long long a = 0, b = 0;
  bool is_ok = true;
  for (long long i = 1; i < n + 1; ++i) {
    if (vals[i] && vals[i - 1]) {
      a++;
    } else if (vals[i] && !vals[i - 1]) {
      b++;
    } else if (!vals[i] && !vals[i - 1] && i != 1) {
      is_ok = false;
      break;
    }
  }
  (!is_ok) ? cout << -1 << "\n" : cout << (5 * a + b + 1) << "\n";
}
int32_t main() {
  clock_t begin = clock();
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  long long t;
  cin >> t;
  while (t--) solve();
  return 0;
}

```