Có ~N~ ô vuông xếp cạnh nhau thành một dãy dài. 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ó hai ô 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 họ 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 hai ô kề nhau không cùng màu. Người số ~1~ là người đi trước.

Ai đến lượt mình mà không chơi được nữa thì thua. Biết họ đều chơi tối ưu nhất có thể, hỏi ai là người thắng cuộc ?

Input

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

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

• Dòng đầu là số nguyên dương ~N \leq 10^5~, số ô vuông.

• Dòng hai là xâu kí tự độ dài ~N~ gồm toàn các kí tự ~0,1,2~ với ý nghĩa :

  • ~0~ - ô chưa được tô.
  • ~1~ - ô đã tô màu trắng.
  • ~2~ - ô đã tô màu đen.

Output

In ra ~T~ dòng các số tự nhiên ~1~ hoặc ~2~, ứng với người thắng ở mỗi test.

Sample Input

2

5
00100

4
1020

Sample Output

2
1