Đạt đã viết ra t số nguyên lên bảng, và Đạt cảm thấy thật tuyệt. Nhưng trong số chúng anh ấy chắc chắn đã viết sai một số nguyên quan trọng, gọi là số nguyên n , và anh ấy cảm thấy không vui chút nào.

Số nguyên n có dạng 10^x (với x ≥ 2), trong đó ký hiệu '^' đại diện cho phép lũy thừa. Nhưng có gì đó đã xảy ra, Đạt đã quên ký hiệu '^' khi tính số nguyên quan trọng này. Ví dụ, thay vì viết giá trị của 10^5, anh ấy lại viết 105, và thay vì 10^19, anh ấy lại viết 1019.

Đạt muốn xác định xem số nguyên nào trong các số trên bảng có thể là số nguyên quan trọng và số nào không.

Đầu vào

• Dòng đầu tiên chứa một số nguyên t (1 ≤ t ≤ 10^4) — số lượng số nguyên trên bảng.
• t dòng tiếp theo, mỗi dòng chứa một số nguyên a (1 ≤ a ≤ 10000) — một trong các số nguyên trên bảng.

Đầu ra

• Với mỗi số nguyên trên bảng, in ra "YES" nếu nó có thể là số nguyên quan trọng, và "NO" nếu không thể.
• Bạn có thể in kết quả bằng bất kỳ dạng chữ nào (viết hoa hoặc viết thường). Ví dụ: "yEs", "yes", "Yes", và "YES" đều được chấp nhận là câu trả lời dương.

Sample Input

7
100
1010
101
105
2033
1019
1002

Sample Output

NO
YES
NO
YES
NO
YES
NO

Ở một vùng đất xa xôi, một chiếc xe buýt có một hàng gồm n ghế, được đánh số từ 1 đến n. Hành khách được khuyên rằng họ nên lên xe và ngồi theo các quy tắc sau:

1. Nếu không có ghế nào đã được ngồi, hành khách có thể ngồi vào bất kỳ ghế trống nào.
2. Nếu đã có ghế bị chiếm, hành khách chỉ được ngồi vào ghế trống mà ghế đó có ít nhất một ghế lân cận đã bị chiếm. Nói cách khác, hành khách có thể ngồi vào ghế số i (với 1 ≤ i ≤ n) chỉ khi ít nhất một trong các ghế số i-1 hoặc i+1 đã có người ngồi.

Hôm nay, n hành khách đã lên xe buýt. Danh sách a ghi lại lần lượt các ghế mà họ đã ngồi. Cụ thể, a1 chứa chỉ số ghế mà hành khách đầu tiên ngồi, a2 chứa chỉ số ghế của hành khách thứ hai, và cứ như vậy.

Bằng một cách nào đấy bạn biết danh sách a. Hãy xác định xem tất cả hành khách có tuân thủ theo các khuyến cáo hay không.

Ví dụ:

Nếu n = 5, và a = [5, 4, 2, 1, 3], thì các khuyến cáo đã không được tuân theo, vì hành khách thứ 3 ngồi vào ghế số 2, trong khi các ghế lân cận với số 1 và 3 đều còn trống.

Đầu vào:

• Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 10^4) — số lượng bộ test.

Mỗi bộ test có định dạng như sau:

• Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 2⋅10^5) — số lượng ghế trên xe buýt và số hành khách đã lên xe.
• Dòng thứ hai chứa n số nguyên phân biệt ai (1 ≤ ai ≤ n) — số ghế mà các hành khách đã ngồi theo thứ tự thời gian.

Đảm bảo rằng tổng của tất cả các giá trị n trong tất cả các test không vượt quá 2*10^5, và không có hành khách nào ngồi vào ghế đã bị chiếm.

Đầu ra:

• Với mỗi test case, in ra "YES" nếu tất cả hành khách tuân thủ quy tắc, và "NO" nếu không.

Sample Input:

4
5
5 4 2 1 3
3
2 3 1
4
2 3 1 4
5
1 2 3 5 4

Sample Output:

NO
YES
YES
NO

Đạt có một mảng a, gọi là mẫu (template), bao gồm n số nguyên. Anh ấy cũng có m chuỗi, mỗi chuỗi chỉ bao gồm các chữ cái Latinh viết thường. Các chuỗi này được đánh số từ 1 đến m. Đạt muốn kiểm tra xem chuỗi nào khớp với mẫu.

Một chuỗi s được coi là khớp với mẫu nếu đồng thời thỏa mãn tất cả các điều kiện sau:

1. Độ dài của chuỗi s bằng với số phần tử trong mảng a.
2. Các số giống nhau trong mảng a tương ứng với các ký tự giống nhau trong chuỗi s. Cụ thể, nếu ai = aj, thì si = sj với mọi 1 ≤ i, j ≤ n.
3. Các ký tự giống nhau trong chuỗi s tương ứng với các số giống nhau trong mảng a. Cụ thể, nếu si = sj, thì ai = aj với mọi 1 ≤ i, j ≤ n.

Nói cách khác, phải có một sự tương ứng một-một giữa các ký tự trong chuỗi và các phần tử trong mảng a.

Ví dụ, nếu a = [3, 5, 2, 1, 3], thì chuỗi "abfda" khớp với mẫu, trong khi chuỗi "afbfa" không khớp, vì ký tự "f" tương ứng với cả số 1 và 5.

Đầu vào:

• Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 10^4) - số lượng bộ test.
  Mỗi bộ test có định dạng như sau:
• Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 2⋅10^5) — số phần tử trong mảng a.
• Dòng thứ hai chứa n số nguyên ai (-10^9 ≤ ai ≤ 10^9) — các phần tử của mảng a.
• Dòng thứ ba chứa số nguyên m (1 ≤ m ≤ 2⋅10^5) — số chuỗi cần kiểm tra.
• Tiếp theo là m chuỗi, mỗi chuỗi sj có độ dài không rỗng (1 ≤ |sj| ≤ 2⋅10^5), chỉ bao gồm các chữ cái Latinh viết thường.

Đảm bảo rằng tổng số n trong tất cả các test không vượt quá 2⋅10^5, và tổng độ dài của tất cả các chuỗi cũng không vượt quá 2⋅10^5.

Đầu ra:

Với mỗi bộ test, in ra m dòng. Ở dòng thứ i (1 ≤ i ≤ m), in ra:

• "YES" nếu chuỗi có chỉ số i khớp với mẫu.
• "NO" nếu không khớp.

Sample Input:

3
5
3 5 2 1 3
2
abfda
afbfa
2
1 2
3
ab
abc
aa
4
5 -3 5 -3
4
aaaa
bcbc
aba
cbcb

Sample Output:

YES
NO
YES
NO
NO
NO
YES
NO
YES

Đạt đã tìm thấy một dải gồm n ô, được đánh số từ trái sang phải từ 1 đến n. Ở ô thứ i, có một số nguyên dương ai và một ký tự si, trong đó tất cả các si đều là 'L' hoặc 'R'.

Đạt mời bạn thử ghi được số điểm tối đa bằng cách thực hiện bất kỳ số lượng phép biến đổi nào (có thể là không thực hiện phép biến đổi nào).

Trong một phép biến đổi, bạn có thể chọn hai chỉ số l và r (1 ≤ l < r ≤ n) sao cho sl = 'L' và sr = 'R', và thực hiện các thao tác sau:

1. Cộng al + al+1 + ... + ar-1 + ar điểm vào tổng điểm hiện tại.
2. Thay thế si bằng ký tự '.' cho tất cả các l ≤ i ≤ r, có nghĩa là bạn không thể chọn các chỉ số này nữa.

Ví dụ:

Xét dải sau:

• Bạn có thể chọn l = 1, r = 2 và cộng 3 + 5 = 8 vào điểm số của mình:

• Sau đó chọn l = 3, r = 6 và cộng 1 + 4 + 3 + 2 = 10 vào điểm số:

Tổng điểm cuối cùng là 18 và không thể thực hiện thêm phép biến đổi nào.

Đầu vào:

• Dòng đầu tiên chứa một số nguyên t (1 ≤ t ≤ 10^4) — số lượng bộ test.
• Dòng đầu tiên của mỗi bộ test chứa một số nguyên n (2 ≤ n ≤ 2⋅10^5) — độ dài của dải ô.
• Dòng thứ hai chứa n số nguyên a1, a2, ..., an (1 ≤ ai ≤ 10^5) — các số được ghi trên dải.
• Dòng thứ ba chứa một chuỗi s gồm n ký tự, mỗi ký tự là 'L' hoặc 'R'.

Đảm bảo rằng tổng của các giá trị n trong tất cả các test không vượt quá 2⋅10^5.

Đầu ra:

• Với mỗi bộ test, in ra một số nguyên — số điểm tối đa có thể ghi được.

Sample Inp

4
6
3 5 1 4 3 2
LRLLLR
2
2 8
LR
2
3 9
RL
5
1 2 3 4 5
LRLRR

Sample Out

18
10
0
22

Hiếu là một học sinh "xuất sắc" tại một trường Tiểu học (có thể là top 1 từ dưới lên🤡). Vào một ngày đẹp trời trong tuần, Hiếu đến lớp và được học về khái niệm "giai thừa" và cách tính số lượng ước nguyên dương của một số. Vì Hiếu rất giỏi, những kiến thức này không thể làm khó Hiếu được. Vậy nên, Hiếu đã nảy ra một câu hỏi thú vị: "Giai thừa của số n sẽ có bao nhiêu ước nguyên dương?"

Tuy nhiên, bài toán này không hề dễ dàng, và với kỹ năng còn non nên Hiếu chưa thể giải được. Các bạn hãy giúp Hiếu giải bài toán này nhé!!!!

Input:

• Một dòng duy nhất chứa số nguyên dương n (1 ≤ n ≤ 10^4).

Output:

• Số lượng ước nguyên dương của n! (giai thừa của n). Kết quả có thể rất lớn, nên hãy in ra phần dư khi chia cho 10^9 + 7.