Giải bài trực tuyến

Có N ô vuông xếp cạnh nhau thành một dãy dài(N<=100000). Một số ô vuông đã được tô màu trắng, một số ô vuông đã được tô màu đen, còn lại là những ô chưa được tô màu. Không có 2 ô kề nhau nào cùng màu.
Hai người cùng chơi một trò chơi, lượt chơi của 2 người xen kẽ nhau. Mỗi người chơi khi đến lượt mình sẽ tô màu vào ô chưa được tô với điều kiện 2 ô kề nhau không cùng màu. Ai đến lượt mình mà không chơi được nữa thì thua. Biết cả 2 người đều chơi tối ưu nhất có thể, hỏi ai là người thắng cuộc.

Input

Input gồm không quá 20 test, dòng đầu là số test. Sau đó là mô tả của các test.
Mỗi test gồm 2 dòng, dòng đầu là số nguyên N, dòng sau ghi N ký tự với ý nghĩa : 0 - ô chưa được tô; 1 - ô đã tô màu trắng; 2 - ô đã tô màu đen.

Output

Ứng với mỗi test ghi một dòng duy nhất là 1 nếu người chơi đầu thắng, 2 nếu người chơi sau thắng.

Example

Input:
2
5
00100
4
1020

Output:
2
1