Để quảng bá cho cuộc thi chạy của Hippo Runners Club, các thành viên ban quản trị đã rất đau đầu để suy nghĩ ra một cái tên thực sự đáng chú ý. Sau nhiều tháng tranh luận, mọi người đã đi đến thống nhất các quy tắc sau:

• Tên cuộc thi chỉ có thể bao gồm các kí tự in thường Latin (a..z).
• Cho trước 2 xâu \(A\) và \(B\), tên bắt buộc phải bắt đầu bằng \(A\) và kết thúc bằng \(B\).
• Độ dài của tên không được vượt quá \(|A|+|B|+k\) (với \(|S|\) là độ dài xâu \(S\)).

Ví dụ: Với A = “abc”, B = “cde”, k = 3. Những tên sau được xem là hợp lệ: “abcxyzcde”, “abcde”, … và những tên sau là không hợp lệ “abxcde”, “abczzzzcde”, “thoi bay covid 123”, …

Cho trước một xâu \(S\), hãy tìm xem liệu có tồn tại xâu con \(X\) của \(S\) (các kí tự liên tiếp) mà \(X\) là một cái tên hợp lệ hay không.

Input

• Dòng đầu tiên gồm \(T (1 \leq T \leq 10)\) là số testcase:
• Mỗi testcase bao gồm 4 dòng:
  • Dòng đầu tiên gồm 1 số nguyên \(k\) duy nhất.
  • Ba dòng tiếp theo gồm 3 xâu \(S, A, B\) trên mỗi dòng. \((1 \leq n_S, n_A, n_B, k \leq 10^5\) và \(max(n_A, n_B) \leq n_S)\) với \(n_x\) là độ dài xâu \(x\).

Output

• Gồm \(T\) dòng ứng với mỗi testcase. In ra YES nếu tồn tại, ngược lại in NO.

Example

3
7
thoibaycovid
thoi
covid
9
abcde
abc
cde
1
abcccd
abc
d 

YES
YES
NO