{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eChúng ta xác định một chuỗi có độ dài \\(l\\) như một mảng \\(S[1..l]\\). Tất cả các phần tử trong đó thuộc một tập hợp hữu hạn \\(\\sum\u003d\\{a,b,...,z\\}\\).\u003c/p\u003e\n\n\u003cp\u003eĐặt \\(\\text{Prefix}(S,i)\u003dS[1..i]\\) là một tiền tố của \\(S\\) với độ dài \\(i\\).\u003c/p\u003e\n\n\u003cp\u003eTương tự, \\(\\text{Suffix}(S,j)\u003dS[j..l]\\) biểu thị một hậu tố của \\(S\\) với độ dài \\(l-j+1\\).\u003c/p\u003e\n\n\u003cp\u003eBây giờ DreamGrid đưa cho bạn một tập hợp chuỗi \\(\\{S_{n}\\}\\) với số phần tử là \\(n\\), và \\(q\\) nhiệm vụ \u003cem\u003ekhông quá khó\u003c/em\u003e:\u003c/p\u003e\n\n\u003cp\u003eĐối với mỗi nhiệm vụ, bạn sẽ nhận được hai số nguyên \\(i, j\\) (\\(i \\ne j\\)) chỉ ra chuỗi thứ \\(i\\) và thứ \\(j\\) trong tập hợp nêu trên. Bạn phải tính chuỗi \\(S^{\u0027}\\) \u003cstrong\u003edài nhất\u003c/strong\u003e thỏa mãn hai điều kiện sau đây cùng một lúc.\u003c/p\u003e\n\u003col\u003e\n \u003cli\u003e\\(S^{\u0027}\\) đồng thời là hậu tố của \\(S_{i}\\) và \\(S_{j}\\)\u003c/li\u003e\n \u003cli\u003eTồn tại ít nhất một chuỗi \\(S_{k}\\in\\{S_{n}\\}\\) sao cho \\(S^{\u0027}\\) là tiền tố của \\(S_{k}\\). Đặt số lượng chuỗi như vậy là \\(|\\{S_{k}\\}|\\) (Rõ ràng, \\(\\{S_{k}\\}\\), cũng là một tập hợp nhiều phần tử, là một tập con của \\(\\{S_{n}\\}\\)).\u003c/li\u003e\n\u003c/ol\u003e\n\n\u003cp\u003eNếu \\(S^{\u0027}\\) như vậy không tồn tại, bạn phải in ra ký tự \u0027N\u0027(không có dấu ngoặc). Ngược lại, chương trình của bạn nên in ra \\(|\\{S_{k}\\}|\\) trên một dòng.\u003c/p\u003e\n\n\u003ch4\u003eNhập\u003c/h4\u003e\n\n\u003cp\u003eCó khoảng 10 bài kiểm tra.\u003c/p\u003e\n\n\u003cp\u003eĐối với mỗi bài kiểm tra, dòng đầu tiên chứa một số nguyên \\(n\\) (\\( 1 \\le n \\le 10^5\\)).\u003c/p\u003e\n\n\u003cp\u003eCác dòng tiếp theo mỗi dòng chứa một chuỗi viết thường \\(S_{i}\\). Chúng tôi đảm bảo rằng \\(1 \\le \\sum_{i\u003d1}^{n}|S_{i}|\\le 5\\times 10^5\\) và mỗi chuỗi không rỗng.\u003c/p\u003e\n\n\u003cp\u003eDòng tiếp theo chứa một số nguyên \\(q\\) (\\(1 \\le q \\le 10^5\\)).\u003c/p\u003e\n\n\u003cp\u003eVà cuối cùng \\(q\\) dòng mỗi dòng chứa hai số nguyên \\(i, j\\) (\\(1 \\le i, j \\le n\\), \\(i \\ne j\\)).\u003c/p\u003e\n\n\u003ch4\u003eXuất\u003c/h4\u003e\n\n\u003cp\u003eĐối với mỗi truy vấn, in câu trả lời theo mô tả trên.\u003c/p\u003e\n\n\u003ch4\u003eVí dụ\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\nab\r\ncb\r\nde\r\n2\r\n1 2\r\n2 3\r\n7\r\nxabcd\r\nyabcd\r\ncdo\r\ncdp\r\ncdq\r\ncdr\r\nabcdz\r\n1\r\n1 2\r\n3\r\naa\r\naa\r\naa\r\n1\r\n1 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eN\r\nN\r\n1\r\n3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}