human
You are given a digital clock with n digits. Each digit shows an integer from 0 to 9, so the whole clock shows an integer from 0 to 10^n-1. The clock will show leading zeroes if the number is smaller than 10^{n-1}.

You want the clock to show 0 with as few operations as possible. In an operation, you can do one of the following: 

  * decrease the number on the clock by 1, or 
  * swap two digits (you can choose which digits to swap, and they don't have to be adjacent). 


Your task is to determine the minimum number of operations needed to make the clock show 0.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^3).

The first line of each test case contains a single integer n (1 ≤ n ≤ 100) — number of digits on the clock.

The second line of each test case contains a string of n digits s_1, s_2, …, s_n (0 ≤ s_1, s_2, …, s_n ≤ 9) — the number on the clock.

Note: If the number is smaller than 10^{n-1} the clock will show leading zeroes.

Output

For each test case, print one integer: the minimum number of operations needed to make the clock show 0.

Example

Input

7
3
007
4
1000
5
00000
3
103
4
2020
9
123456789
30
001678294039710047203946100020

Output

7
2
0
5
6
53
115

Note

In the first example, it's optimal to just decrease the number 7 times.

In the second example, we can first swap the first and last position and then decrease the number by 1.

In the third example, the clock already shows 0, so we don't have to perform any operations.
The above is tricky. Write me a correct solution in PYTHON3.
 What is a Python program to determine the minimum number of operations needed to make the clock show 0?
assistant
#Here is Python program to determine the minimum number of operations needed to make the clock show 0.

import os, sys, math
from io import BytesIO, IOBase
ip = lambda: input()
it = lambda: int(input())
ma = lambda: map(int, input().split(" "))
li = lambda: list(map(int,input().split(" ")))
mod=10**9+7
md=998244353

def f(x):
    z=0
    l=len(x)
    for i in range(l):
        z+=int(x[i])+1
    return z-1

def main():
    for _ in range(int(input())):
        n=it()
        arr=[int(x) for x in ip()]
        z=0
        for i in range(n):
            a=arr[i]
            if a:
                z+=a+1
        if arr[-1]:
            z-=1
        print(z)


    # Fast IO Region
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
     ...