Một công cụ phân tích từ vựng cần thống kê mức độ phổ biến của các tiền tố trong tập tài liệu. Bạn hãy xây dựng hệ thống hỗ trợ hai loại yêu cầu:

• 1 S: Thêm một từ \(S\) vào cơ sở dữ liệu.
• 2 P: Cho biết có bao nhiêu từ trong cơ sở dữ liệu bắt đầu bằng tiền tố \(P\).

Định dạng đầu vào

• Dòng đầu chứa số nguyên dương \(Q\) (\(1 \le Q \le 10^5\)) — số lượng thao tác.
• \(Q\) dòng tiếp theo, mỗi dòng chứa một thao tác theo định dạng.

Định dạng đầu ra

• Với mỗi thao tác loại 2, in ra số lượng từ thỏa mãn trên một dòng riêng.

Ví dụ

Input:

6
1 apple
1 app
2 app
1 apricot
2 ap
2 b

Output:

2
3
0

Ràng buộc

• 30% số điểm ứng với \(Q \le 1000\) và tổng độ dài xâu \(\le 5000\).
• 70% số điểm còn lại có tổng độ dài các xâu không vượt quá \(10^6\). Các ký tự chỉ chứa chữ cái tiếng Anh in thường.