Trò chơi đen trắng

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Ðược add lên bởi Khúc Anh Tuấn
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.