Koi và Kon thi đấu với nhau bằng một trò chơi trí tuệ trên xâu kí tự $S$. Mỗi người lần lượt chọn và xóa bỏ một đoạn xâu tiền tố gồm các kí tự giống nhau trên xâu $S$. Ví dụ, với xâu $aaabbb$, người chơi có thể xóa xâu $aa$ ở đầu xâu $S$ để thu được xâu $abbb$.

Người chiến thắng là người đi lượt cuối cùng. Bạn hãy lập trình thuật toán xác định kết quả của ván đấu khi Koi và Kon đều chơi tối ưu.

Đầu vào

Dòng đầu tiên chứa số nguyên $t$, số lượng test con. $t$ dòng tiếp theo, mỗi dòng chứa một xâu kí tự $S$ (chỉ gồm toàn các chữ cái thường).

Tổng các kí tự của các xâu $S$ không vượt quá ${10}^6$.

Đầu ra

$t$ dòng, mỗi dòng chứa kết quả của một ván đấu: xuất ra $1$ nếu người thứ nhất chiến thắng, $2$ nếu người thứ hai chiến thắng.

Subtask

$50\mathrm{\%}$ số test có $t\le 100$ và các xâu có độ dài $\le 100$.

Ví dụ

Đầu vào:

2
aabb 
baaa

Đầu ra:

1
2

Giải thích: Trong ván đấu thứ hai, trò chơi có thể diễn ra như sau:

• Người thứ nhất xóa xâu $b$ (nước đi hợp lệ duy nhất).
• Người thứ hai xóa xâu $aaa$, kết thúc trò chơi.