#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int d4x[4] = {1, 0, -1, 0};
int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
template <class X, class Y>
bool minimize(X &x, const Y &y) {
  if (x > y) {
    x = y;
    return true;
  }
  return false;
}
template <class X, class Y>
bool maximize(X &x, const Y &y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}
const int MOD = 1e9 + 7;
template <class X, class Y>
void add(X &x, const Y &y) {
  x = (x + y);
  if (x >= MOD) x -= MOD;
}
template <class X, class Y>
void sub(X &x, const Y &y) {
  x = (x - y);
  if (x < 0) x += MOD;
}
const ll INF = 1e9;
const int N = 1e5 + 10;
int a[N];
void solve() {
  int n;
  cin >> n;
  int len = 1;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (len == -1) continue;
    if (a[i] == 1)
      if (a[i - 1] == 1)
        len += 5;
      else
        len++;
    if (i > 1 && a[i] == 0 && a[i - 1] == 0) len = -1;
  }
  cout << len << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int tc = 1, ddd = 0;
  cin >> tc;
  while (tc--) {
    solve();
  }
}

### Prompt

In Cpp, your task is to solve 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;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int d4x[4] = {1, 0, -1, 0};
int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
template <class X, class Y>
bool minimize(X &x, const Y &y) {
  if (x > y) {
    x = y;
    return true;
  }
  return false;
}
template <class X, class Y>
bool maximize(X &x, const Y &y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}
const int MOD = 1e9 + 7;
template <class X, class Y>
void add(X &x, const Y &y) {
  x = (x + y);
  if (x >= MOD) x -= MOD;
}
template <class X, class Y>
void sub(X &x, const Y &y) {
  x = (x - y);
  if (x < 0) x += MOD;
}
const ll INF = 1e9;
const int N = 1e5 + 10;
int a[N];
void solve() {
  int n;
  cin >> n;
  int len = 1;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (len == -1) continue;
    if (a[i] == 1)
      if (a[i - 1] == 1)
        len += 5;
      else
        len++;
    if (i > 1 && a[i] == 0 && a[i - 1] == 0) len = -1;
  }
  cout << len << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int tc = 1, ddd = 0;
  cin >> tc;
  while (tc--) {
    solve();
  }
}

```