Cho \(P\) là tập hợp chứa các xâu gồm chữ cái in thường. Ban đầu, tập hợp \(P\) rỗng.

Cho \(Q\) truy vấn, mỗi truy vấn là một trong hai loại sau:

• \(1\) \(s\): Thêm xâu \(s\) vào tập hợp \(P\)
• \(2\) \(s\): In ra số lần xuất hiện của xâu \(s\) trong tập hợp \(P\).

Yêu cầu

Với mỗi truy vấn loại 2, in ra số lần xuất hiện thỏa mãn.

Input

• Dòng đầu tiên chứa số nguyên dương \(Q\) \((1 ≤ Q ≤ 10000)\) −Số lượng truy vấn.
• \(Q\) dòng tiếp theo mỗi dòng chứa một số nguyên dương 1 hoặc 2 thể hiện loại truy vấn, và một xâu \(s\) \((|s| ≤ 100).\)

Output

Với mỗi truy vấn loại 2, in ra trên các dòng khác nhau kết quả tương ứng.

Example

Gợi ý: Sử dụng Map để đánh dấu số lần xuất hiện của xâu.