Cho một dãy nhị phân độ dài ~N~. Xét trò chơi giữa hai người như sau: đến lượt mình, người chơi xóa ~K~ số ~1~ liên tiếp nhau trong dãy. Trò chơi kết thúc khi có một người không thể xóa được nữa, đó là người thua cuộc. Người chơi số ~1~ luôn đi trước.

Lưu ý: Nếu như ngay từ đầu người đi trước đã không xóa được thì thua luôn và trò chơi kết thúc.

Xác định xem ai chắc chắn là người thắng cuộc. Biết rằng hai người đều chơi tối ưu.

Input

Dòng đầu tiên là số nguyên dương ~T \leq 100~, số test.

Sau đó là ~T~ test, mỗi test gồm ~2~ dòng, trong đó:

• Dòng thứ nhất là số ~K \leq 10~.
• Dòng thứ hai là xâu nhị phân không rỗng độ dài ~N \leq 1000~.

Output

Gồm T dòng, mỗi dòng ghi ra người chiến thằng (~1~ hoặc ~2~) của test đó.

Sample Input

2
2
0011101101
1
11111111111

Sample Output

2
1