Yêu cầu: Một chuỗi số được gọi là hoàn hảo nếu nó không rỗng và tần số xuất hiện của từng kí tự trong chuỗi đó không lớn hơn số lượng kí tự phân biệt trong nó .

Cho 1 chuỗi s có độ dài n ,chứa có các kí tự số từ 0 đến 9 .Tìm số lượng chuỗi con hoàn hảo trong s.

Một chuỗi a được gọi là chuỗi con của b nếu a được lấy từ b bằng việc xóa đi (1 vài hoặc 0) kí tự đầu và xóa đi (1 vài hoặc 0) kí tự cuối của chuỗi b.

Input

• Dòng đầu chứa số nguyên t thể hiện số test case ~( 1 ≤ t ≤ 10)~.
• Dòng đầu tiên của mỗi testcase chứa n – độ dài của chuỗi s ~(1 ≤ n ≤ 10^5)~.
• Dòng thứ hai của testcase chứa chuỗi s có độ dài n (chỉ chứa các kí tự 0 đến 9).

Output

In ra t dòng .Mỗi dòng là số lượng chuỗi con hoàn hảo của chuỗi s.

Giới hạn

• Không có giới hạn gì thêm

Ví dụ

Sample input

1

2

77

Sample output

2