Cho hai xâu ~s~ và ~t~ có cùng độ dài ~c~, sự khác biệt của chúng được xác định là số vị trí ~i~ mà ~s[i] <> t[i]~.

Cho ~n~ xâu ký tự có cùng độ dài và chỉ gồm các ký tự 'H' và 'G', hãy lập trình xác định sự khác biệt lớn nhất của mỗi xâu đối với các xâu còn lại trong ~n~ xâu đã cho.

Input

Dòng đầu tiên chứa hai số nguyên ~c~ và ~n~ thỏa ~1 \le c \le 18; 2 \le n \le 10^5~.

~n~ dòng tiếp theo, mỗi dòng chứa một xâu độ dài ~c~.

Output

Ứng với mỗi xâu in ra sự khác biệt lớn nhất của nó với các xâu còn lại.

Samples

Sample Input

5 3
HHGGH
HHHHH
HGHHG

Sample Output

4 
2
4