Cho một xâu ~S~ độ dài ~N~, chỉ gồm các ký tự:

• chữ cái in hoa ~A~ đến ~Z~
• chữ cái in thường ~a~ đến ~z~
• chữ số ~0~ đến ~9~

Một xâu được gọi là mạnh nếu đồng thời thỏa mãn cả ~4~ điều kiện sau:

• có ít nhất ~6~ ký tự
• có ít nhất ~1~ chữ cái in hoa
• có ít nhất ~1~ chữ cái in thường
• có ít nhất ~1~ chữ số

Yêu cầu

Đếm số cặp ~\left(L,R\right)~ sao cho xâu con liên tiếp từ vị trí ~L~ đến vị trí ~R~ là một xâu mạnh.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~N~
• Dòng thứ hai chứa xâu ~S~ gồm đúng ~N~ ký tự

Kết quả

In ra một số nguyên duy nhất là số lượng xâu con mạnh.

Ví dụ

Ví dụ 1

Input

27
OrepYorsr9cNNEJMWbPmd8kYrSr

Output

221

Ví dụ 2

Input

42
vLOPmn0MIa6eD7LazNoocSDjZCjGzcAvnHKvV5Tlxp

Output

531

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 10^6~

Chấm điểm

• Có ~40%~ số test có ~N \le 500~
• Có ~30%~ số test khác có ~N \le 1000~
• Có ~30%~ số test còn lại không có ràng buộc gì thêm