Hôm nay Mbappe, Morata, Bale đang solo đá bóng với nhau. Họ đều là những cầu thủ với khả năng sút bóng siêu đỉnh, bách phát bách trúng. Đá mãi với nhau mà không phân định thắng thua nên họ đã quyết định solo đá luân lưu.

Luật chơi như sau :

• Bọn họ chia bao gồm 2 đội (Do Mbappe đá luân lưu quá hay nên anh chấp hẳn mình một đội còn Morata và Bale về đội bên kia).
• Ban đầu có NN quả bóng.
• 2 đội đá luân phiên, đội của Mbappe đi trước, trong mỗi lượt đá của một đội, mỗi người chơi trong đội đó sẽ lần lượt sút một quả bóng (vì họ sút cực chuẩn nên tỉ lệ vào là 100%)
• Trò chơi kết thúc khi không còn quả bóng nào.
• Đội chiến thắng là đội sút được nhiều bóng hơn.

Cho biết số bóng ban đầu, bạn hãy dự đoán kết quả của trận đấu nhé!

Input

• Dòng đầu gồm số nguyên dương \(T\) (\(T \leq 10^5\)) là số ván đấu xảy ra

• \(T\) dòng tiếp theo, mỗi dòng là một số nguyên không âm (\(0≤N≤10^9\)) cho biết số bóng ban đầu của ván đấu tương ứng.

Output

• Gồm \(T\) dòng, dòng thứ \(i\) gồm \(1\) số nguyên là kết quả của trận đấu thứ \(i\). Xuất 1 nếu Mbappe thắng, xuất 2 nếu Mbappe thua, và xuất 0 nếu cả hai đội hòa

Example

3
3
2

2
0