Tìm chuỗi kí tự

Bảng chữ cái tiếng Anh có \(26\) kí tự từ A' đếnZ'; có \(5\) nguyên âm là A',E', I',O', `U'; các kí tự còn lại là phụ âm. Cho một xâu \(S\) chỉ gồm các chữ cái in hoa.

• Bài toán loại 1: đếm số cách chọn bộ ba vị trí \((i, j, k)\) trong xâu \(S\) để ghép đúng thứ tự chọn và tạo thành xâu ``HSG''. Với \(1 \le i < j < k \le L\); \(L\) là độ dài xâu \(S\).

• Bài toán loại 2: yêu cầu như Bài toán loại 1, nhưng có thêm ràng buộc là các kí tự có vị trí ở giữa bộ \(3\) chỉ số đó không là kí tự nguyên âm.

Input

Dữ liệu vào từ bàn phím gồm:

• Dòng 1: chứa số nguyên dương \(T\). Nếu \(T = 1\) thì giải bài toán loại 1. Nếu \(T = 2\) thì giải bài toán loại 2.

• Dòng 2: chứa xâu \(S\) có độ dài không quá \(10^5\).

Ràng buộc:

• Có \(40\%\) số test có \(T = 1\), xâu \(S\) dài không quá \(100\) kí tự.

• Có \(40\%\) số test khác có \(T = 2\), xâu \(S\) dài không quá \(100\) kí tự.

• Có \(20\%\) số test còn lại có xâu \(S\) dài không quá \(10^5\) kí tự.

Output

Ghi ra kết quả giải bài toán tương ứng với dữ liệu vào.

Example 1

Input:

1
HSEHSG

Output:

3

Example 2

Input:

2
HSEHSG

Output:

1

Note

Ví dụ 1: giải bài toán loại 1, có \(3\) bộ vị trí tìm được là \((1,2,6)\), \((1,5,6)\), \((4,5,6)\) ghép được xâu ``HSG''.

Ví dụ 2: giải bài toán loại 2, có \(1\) bộ vị trí tìm được là \((4,5,6)\) ghép được xâu ``HSG''.