human
What is a Python program to determine what happened with his flower in the end given the following:
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
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is Python program to determine what happened with his flower in the end.

### Codeforces handle - "@titanalpha"
#Email id - shubhamnokiafan@gmail.com

from collections import Counter, deque
import math
from random import randint
from bisect import bisect
import sys
import re
import copy
from decimal import Decimal,getcontext
getcontext().prec = 32

MOD = 1000000007
MAX = sys.maxsize
MIN = -sys.maxsize
prime = []

class get:
    def int():
        return list(map(int,input().split()))
    def str():
        return input().split()
    def float():
        return list(map(float,input().split()))
    def map():
        return map(int,input().split())

def sqrt(x):
    return int(math.sqrt(x))+1

def gcd(*args):
    result = args[0]
    for item in args:
        result = math.gcd(result,item)
    return result

def LCM(a,b):
    return (a*b)//(math.gcd(a,b))

def isPrime(n):
    if n == 1:
        return False
    for i in range(2,sqrt(n)):
        if n%i == 0:
            return False
    return True

def solve():
    n = int(input())
    a = get.str()
    a = "".join(a)
    if "00" in a:
        print(-1)
        return
    res = 1
    for i in range(n):
        if a[i] == "1":
            if i == 0:
                res += 1
            elif a[i-1] == "1":
                res += 5
            else:
                res += 1
    print(res)

for _ in range(int(input())):
    solve()