Bàn Cờ Logic

Minh và Nam cùng tham gia một trò chơi đối kháng trên một dãy gồm $n$ giá trị chân lý. Mỗi giá trị nhận trạng thái đúng hoặc sai, được biểu diễn bằng một chuỗi nhị phân độ dài $n$ (trong đó ký tự 1 tương ứng với giá trị đúng, và ký tự 0 tương ứng với giá trị sai). Ban đầu, giữa các giá trị chân lý không có toán tử nào.

Minh và Nam lần lượt thực hiện lượt đi bằng cách đặt toán tử AND hoặc OR vào giữa hai giá trị chân lý liền kề chưa có toán tử, trong đó Minh là người đi trước. Trò chơi sẽ kết thúc sau đúng $n - 1$ lượt đi. Mục tiêu của Minh là làm cho biểu thức hoàn chỉnh cuối cùng nhận giá trị đúng, trong khi Nam muốn biểu thức đó nhận giá trị sai. Giả sử cả hai người chơi đều thi đấu tối ưu, hãy xác định xem Minh có chắc chắn giành chiến thắng hay không.

Để tính giá trị của biểu thức logic cuối cùng, các phép toán được thực hiện lặp lại theo quy tắc sau cho đến khi chỉ còn lại một giá trị duy nhất:

• Nếu biểu thức còn chứa toán tử AND, hãy chọn một toán tử AND bất kỳ và thay thế biểu thức con gồm toán tử đó cùng hai toán hạng hai bên bằng giá trị của phép toán.
• Nếu không còn toán tử AND nào, biểu thức chỉ còn lại toán tử OR. Hãy chọn một toán tử OR bất kỳ và thay thế biểu thức con gồm toán tử đó cùng hai toán hạng hai bên bằng giá trị của phép toán.

Ví dụ, biểu thức đúng OR sai AND sai được tính thành đúng OR (sai AND sai) = đúng OR sai = đúng. Người ta đã chứng minh được rằng thứ tự tính toán giữa các toán tử cùng loại không làm thay đổi kết quả cuối cùng của biểu thức.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $t$ ($1 ≤ t ≤ 10^4$) biểu thị số lượng bộ dữ liệu.

Mỗi bộ dữ liệu bao gồm hai dòng:

• Dòng thứ nhất chứa số nguyên $n$ ($2 ≤ n ≤ 2 · 10^5$, tổng $n$ qua tất cả các bộ dữ liệu không vượt quá $2 · 10^5$, tức $\sum n ≤ 2 · 10^5$) biểu thị độ dài của chuỗi nhị phân.
• Dòng thứ hai chứa một chuỗi nhị phân độ dài $n$ chỉ gồm các ký tự 0 và 1 biểu diễn dãy các giá trị chân lý ban đầu.

Kết quả

Với mỗi bộ dữ liệu, in ra "YES" (không có dấu ngoặc kép) nếu Minh giành chiến thắng, ngược lại in ra "NO" (không có dấu ngoặc kép).

Bạn có thể in các chữ cái dưới dạng chữ hoa hoặc chữ thường (ví dụ, các chuỗi "yES", "yes", "Yes" đều được chấp nhận là câu trả lời hợp lệ).

Chấm điểm

Subtask 1 (25 points). $n ≤ 11$; $\sum n ≤ 200$

Subtask 2 (75 points). $1 ≤ t ≤ 10^4$; $2 ≤ n ≤ 2 · 10^5$; $\sum n ≤ 2 · 10^5$

Ví dụ

Input

5
2
11
3
010
12
101111111100
10
0111111011
8
01000010

Output

YES
NO
YES
YES
NO

Ghi chú

Ở bộ dữ liệu thứ nhất, Minh có thể đặt toán tử AND vào giữa hai giá trị chân lý. Trò chơi kết thúc do không còn vị trí nào để đặt thêm toán tử, và Minh chiến thắng vì đúng AND đúng cho kết quả là đúng.

Ở bộ dữ liệu thứ hai, Minh có thể đặt toán tử OR vào giữa giá trị đúng ở giữa và giá trị sai bên trái. Sau đó Nam có thể đặt toán tử AND vào giữa giá trị đúng ở giữa và giá trị sai bên phải. Biểu thức sai OR đúng AND sai cho kết quả là sai.

Lưu ý rằng những nước đi trong ví dụ trên chỉ nhằm mục đích minh họa và không nhất thiết là chiến thuật tối ưu của Minh hay Nam.