Bạn được cho một mảng a gồm n số nguyên, mỗi phần tử là một chữ số từ 0 đến 9.

Một mảng con được gọi là tốt nếu tổng các phần tử trong mảng con đó bằng đúng độ dài của mảng con.

Ví dụ: Với mảng a = [1, 2, 0], các mảng con tốt là:

[1] (tổng = 1, độ dài = 1)

[2, 0] (tổng = 2, độ dài = 2)

[1, 2, 0] (tổng = 3, độ dài = 3)

→ Có 3 mảng con tốt.

Đầu vào:

Dòng đầu tiên là số nguyên ~t~ ~(1 ≤ t ≤ 1000)~ — số lượng test case.

Với mỗi test case:

Dòng đầu tiên là số nguyên n ~(1 ≤ n ≤ 10⁵)~ — độ dài mảng.

Dòng thứ hai là một chuỗi gồm n chữ số, mỗi chữ số biểu diễn một phần tử trong mảng a.

Đảm bảo: Tổng độ dài n của tất cả test case không vượt quá ~10⁵~.

Đầu ra:

Với mỗi test case, in ra một dòng duy nhất là số lượng mảng con tốt trong mảng đã cho.

Ví dụ :

Input:

3
3
120
5
11011
6
600005

Output:

3
6
1