Từ khi Khánh trở thành tỉ phú, Khánh liên tục vác con xe F1 của mình đi dạo quanh thành phố của Nam, nơi Nam ban hành lệnh bỏ cấm xe F1. Mỗi khi Khánh đến thành phố của Nam, Nam đều cho cấm dân sử dụng phương tiện gắn máy khác để Khánh có thể phóng thoải mái.

Để thông báo kịp thời, tại ~n~ con đường dẫn đến thành phố của Nam, mỗi con đường Nam lắp đặt 1 thiết bị ghi thanh để nhận dạng tiếng xe của Khánh. Bản ghi tiếng xe ở mỗi con đường là một xâu gồm các kí tự trong bảng chữ cái Alphabet bao gồm cả in hoa lẫn in thường. Có thể nhận biết được tiếng xe của Khánh miễn là trong bản ghi tồn tại ít nhất 1 xâu con liên tiếp có dạng:

• Xâu con phải bắt đầu với một dãy khác rỗng liên tiếp chỉ gồm kí tự ~b~ hoặc ~B~
• Ngay sau đó là một dãy khác rỗng liên tiếp chỉ gồm kí tự ~r~ hoặc ~R~
• Ngay sau đó là một dãy khác rỗng liên tiếp chỉ gồm kí tự ~u~ hoặc ~U~
• Ngay sau đó là một dãy khác rỗng liên tiếp chỉ gồm kí tự ~h~ hoặc ~H~
• Ngay sau đó là một dãy khác rỗng liên tiếp chỉ gồm kí tự ~m~ hoặc ~M~

Ví dụ: ~“jhdsbbBBrRruuuhhHMMMsd”~, ~“bruhm”~, ~“SADJBRUHM”~ đều được coi là có tiếng xe của Khánh, nhưng ~“sdgBRasdUHM”~, ~“RrrBBbUhm”~ thì không.

Hãy giúp Nam tìm xem trong tất cả ~n~ con đường, những con đường nào có xe của Khánh đi qua.

Input

Dòng đầu tiên chứa 1 số ~n~ ~(1≤n≤10^{6})~ , là số lượng con đường đến thành phố của Nam.

Trong ~n~ dòng tiếp theo, mỗi dòng chứa 1 xâu ~s_i~ ~(|s_i|≤10^6)~ là bản ghi ở con đường thứ ~i~.

Lưu ý: Đề bài đảm bảo tổng độ dài các xâu không vượt quá ~10^6~.

Output

Với mỗi bản ghi , trên dòng thứ in ra ~1~ nếu trong bản ghi nhận ra được xe của Khánh, in ra ~0~ nếu ngược lại.

Sample Input

5
jhdsbbBBrRruuuhhHMMMsd
SADJBRUHM
RrrBBbUhm
Bruhm
sdgBRasdUHM

Sample Output

1
1
0
1
0