## Algorithm

A. Countdown
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a digital clock with n digits. Each digit shows an integer from 00 to 99, so the whole clock shows an integer from 00 to 10n110�−1. The clock will show leading zeroes if the number is smaller than 10n110�−1.

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

• decrease the number on the clock by 11, 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 00.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1t1031≤�≤103).

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

The second line of each test case contains a string of n digits s1,s2,,sn�1,�2,…,�� (0s1,s2,,sn90≤�1,�2,…,��≤9) — the number on the clock.

Note: If the number is smaller than 10n110�−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 00.

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

output
Copy
7
2
0
5
6
53
115

Note

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

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

In the third example, the clock already shows 00, so we don't have to perform any operations.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include<iostream>
#include<string>
using namespace std;

int main(){
int t;
cin>>t;
int n, steps;
string s;
while(t--){
cin>>n;
cin>>s;
steps = 0;
for(int i = 0; i < n-1; i++){
if(s[i] != '0'){
steps += (s[i] - '0') + 1;
}
}
steps += (s[n-1] - '0');
cout<<steps<<endl;
}
return 0;
}
Copy The Code &

Input

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

Output

cmd
7
2
0
5
6
53
115