Khánh có mảng ~a~ gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Khánh có thể thực hiện thao tác sau với bất kỳ số lần nào:

• Chọn ~i~, ~j~ ~(i \ne j)~ sao cho ~|a_i − a_j| \le 1~
• Xóa phần tử nhỏ hơn trong ~2~ số (~a_i~ hoặc ~a_j~). Nếu ~2~ số bằng nhau, có thể xóa bất kỳ số nào.

Bạn hãy giúp Khánh xác định xem có thể thu được mảng ~a~ chỉ còn ~1~ phần tử sau một số lần thực hiện thao tác trên hay không?

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 50)~
• Dòng tiếp theo chứa ~n~ phần tử ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 150)~

Output

• In ra YES nếu có thể hoặc NO nếu không thể.

Sample Input

3
1 2 2

Sample Output

YES

Subtask

• ~40\%~ số test có ~1 \le n \le 5~.
• ~60\%~ số test còn lại không có điều kiện gì thêm.

Giải thích

• Đầu tiên chọn ~i = 1~, ~j = 3~, ta có ~|a_1 - a_3| \le 1~, số nhỏ hơn là ~a_1~. Dãy sau khi xóa ~a_1~ là ~[2, 2]~.
• Tiếp tục chọn ~i = 1~, ~j = 2~. Dãy cuối cùng là ~[2]~.

Sáng sớm tinh mơ, iostream tỉnh giấc. Để có năng lượng cho cả một ngày dài, iostream sẽ làm một bữa sáng đủ chất dinh dưỡng. Bữa sáng của iostream gồm có ~n~ quả trứng luộc. Trong quá trình luộc trứng, iostream nghĩ ra một cách để luộc trứng chín đều nhất: trong giây thứ ~i~, cô sẽ lật những quả trứng có số thứ tự là bội của ~i~. Trứng sẽ chín hết sau ~n~ giây. iostream muốn hỏi các bạn, sau ~n~ giây, quả trứng thứ ~n~ sẽ úp hay ngửa? Cho biết, lúc đầu các quả trứng đều ở trạng thái ngửa.

Input

• Dòng đầu tiên của dãy chứa số nguyên dương ~t~ - số bộ test (~t \le 10~).
• ~t~ dòng tiếp theo, mỗi dòng chứa số ~n~, số trứng của iostream (~1 \le n \le 10^{18}~).

Output

• ~t~ dòng, mỗi dòng chứa trạng thái của quả trứng thứ ~n~. Nếu trứng úp thì in ra 1. Nếu trứng ngửa, in ra 0.

Sample Input

2
4
5

Sample Output

1
0

Subtask

• ~30\%~ số test có ~n \le 1000~.
• ~30\%~ số test tiếp theo có ~n \le 10^9~.
• ~40\%~ số test còn lại không có điều kiện gì thêm.

Hôm nay, các thành viên của team Bedao chơi trò tìm chữ cùng với nhau. Đầu tiên, mỗi người sẽ nhận được một bảng gồm ~N~ hàng và ~M~ cột, mỗi ô trong bảng bao gồm một chữ cái và một danh sách gồm ~Q~ từ cần tìm kiếm. Mục tiêu của trò chơi là kiểm tra xem các từ trong danh sách đã cho có được giấu trong bảng hay không. Một từ có thể được đặt theo hướng dọc từ trên xuống dưới, ngang từ trái sang phải, chéo từ trên trái đến dưới phải, chéo từ trên phải đến dưới trái, hoặc theo hướng ngược lại với một trong các hướng đã nêu trên bảng.

Mike cũng tham gia trò chơi này và rất muốn thắng để giành được phần quà hấp dẫn. Tuy vậy, cậu đang bị anh Fat dí deadline nên không thể tham gia. Vậy nên, Mike đã nhờ bạn tìm hộ cậu những từ đó trên bảng. Hãy giúp Mike!

Input

• Dòng đầu tiên gồm ba số ~N, M, Q~ ~(1 \le N, M \le 100, 1 \le Q \le 10)~ lần lượt là độ dài hai chiều của bảng và số từ có trong danh sách.

• ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ chữ cái latinh viết thường thể hiện bảng chữ được cho.

• ~Q~ dòng tiếp theo, dòng thứ ~i~ gồm một xâu ~S_i~ gồm các chữ cái latinh viết thường là chữ cần tìm thứ ~i~ ~(1 \le |S| \le \max(n, m))~.

Output

• In ra ~Q~ dòng, dòng thứ ~i~ in ra YES nếu như xâu ~S_i~ xuất hiện trong bảng và NO nếu ngược lại.

Sample Input

5 6 3
binimo
zenbag
awddaf
qleamw
obytox
bedao
mini
eight

Sample Output

YES
YES
NO

Subtask

• 40% số test có ~n = 1~.
• 60% số test còn lại không có điều kiện gì thêm.

Cho ~2~ số nguyên dương ~n~ và ~k~, hỏi có tồn tại dãy gồm ~n~ số nguyên dương không quá ~k~ sao cho không bộ ba số nào trong dãy là độ dài các cạnh của một tam giác có diện tích dương.

Input

• Dòng đầu tiên chứa số nguyên ~t~ là số test case. ~(1 \le t \le 10^5)~
• ~t~ dòng sau, mỗi dòng gồm ~2~ số nguyên lần lượt là ~n~ và ~k~. ~(3 \le n \le 10^{18}, 1 \le k \le 10^{18})~

Output

• Gồm ~t~ dòng tương ứng với kết quả mỗi test case, nếu tồn tại một dãy thỏa mãn, in ra yes, ngược lại in ra no.

Sample Input

2
4 2
3 3

Sample Output

no
yes

Subtask

• ~30\%~ số test có ~t \le 10, k \le 8~
• ~70\%~ số test còn lại không có điều kiện gì thêm

Giải thích

• Với ~n = 4, k = 2~, không tồn tại dãy nào thỏa mãn.
• Với ~n = 3, k = 3~, ta có dãy ~[1, 2, 3]~ thỏa mãn.

Cho hai số nguyên dương ~n~ và ~m~, hãy đếm số lượng cặp số nguyên ~(a,b)~ thỏa mãn điều kiện sau:

• ~a\times b \leq m~
• ~1\leq a < b \leq n~
• ~a\times b~ là số chính phương

Input

• Dòng đầu chứa số nguyên dương ~n~ (~1 \le n \le 10^{7}~).
• Dòng thứ hai chứa số nguyên dương ~m~ (~1 \le m \le 10^{14}~).

Output

• Một số nguyên duy nhất là số lượng cặp số thỏa mãn.

Sample Input

4
4

Sample Output

1

Subtask

• ~20\%~ số test có ~n \le 3\,000~
• ~20\%~ số test tiếp theo có ~n \le 10^5, m \le 10^6~
• ~30\%~ số test tiếp theo có ~n \le 10^6~
• ~30\%~ số test còn lại không có điều kiện gì thêm

Giải thích

Cặp số duy nhất thỏa mãn là ~a=1,b=4~