Bạn được cho một dãy ~a~ gồm các số nguyên từ ~0~ tới ~9~. Một dãy ~a~ được gọi là tốt khi và chỉ khi tổng của dãy đó bằng số phần tử của dãy đó (~\sum_{i=l}^{r} a_i = r - l + 1~).

Ví dụ, với dãy ~a = [1, 2, 0]~, có ~3~ dãy tốt: ~[1]~, ~[2, 0]~, ~[1, 2, 0]~.

Hãy đếm số dãy con liên tiếp là dãy tốt trong dãy ~a~.

Input

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 1000~) là số lượng test.

Dòng đầu tiên của mỗi test gồm số nguyên dương ~n~ (~1 \le n \le 10^5~) là số phần tử của dãy ~a~.

Dòng thứ hai của mỗi test gồm ~n~ chữ số được viết liền nhau, là các phần tử trong dãy.

Dữ liệu đảm bảo tổng của ~n~ qua mọi test không vượt quá ~10^5~.

Output

Với mỗi test in ra một số nguyên, là số dãy con liên tiếp là dãy tốt trong dãy ~a~.

Sample Input 1

2
5
12321
4
1023

Sample Output 1

2
3

Notes

Trong test đầu tiên, có hai dãy tốt là ~[1, 1]~ và ~[5, 5]~.

Trong test thứ hai, có ba dãy tốt là ~[1, 1]~, ~[1, 3]~ và ~[2, 3]~.