{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eLần này Baby Ehab chỉ cắt và không dán. Anh ấy bắt đầu với một mảnh giấy có một mảng $$$a$$$ có độ dài $$$n$$$ được viết trên đó, và sau đó anh ấy thực hiện các bước sau:\u003c/p\u003e\u003cul\u003e \u003cli\u003e anh ấy chọn một khoảng $$$(l, r)$$$ và cắt đoạn con $$$a_l, a_{l + 1}, \\ldots, a_r$$$ ra, loại bỏ phần còn lại của mảng. \u003c/li\u003e\u003cli\u003e sau đó anh ấy cắt khoảng này thành nhiều khoảng con. \u003c/li\u003e\u003cli\u003e để thêm gia vị lý thuyết số vào, anh ấy yêu cầu rằng các phần tử của mỗi khoảng con phải có tích của chúng bằng với \u003ca href\u003d\"https://en.wikipedia.org/wiki/Least_common_multiple\"\u003ebội chung nhỏ nhất (LCM)\u003c/a\u003e của chúng. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eVề mặt chính thức, anh ấy phân chia các phần tử của $$$a_l, a_{l + 1}, \\ldots, a_r$$$ thành các mảng con liên tiếp sao cho tích của mỗi mảng con bằng với LCM của nó. Bây giờ, đối với $$$q$$$ khoảng độc lập $$$(l, r)$$$, hãy cho Baby Ehab biết số lượng mảng con tối thiểu mà anh ấy cần.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa $$$2$$$ số nguyên $$$n$$$ và $$$q$$$ ($$$1 \\le n,q \\le 10^5$$$)\u0026nbsp;— độ dài của mảng $$$a$$$ và số lượng truy vấn.\u003c/p\u003e\u003cp\u003eDòng tiếp theo chứa $$$n$$$ số nguyên $$$a_1$$$, $$$a_2$$$, $$$\\ldots$$$, $$$a_n$$$ ($$$1 \\le a_i \\le 10^5$$$)\u0026nbsp;— các phần tử của mảng $$$a$$$.\u003c/p\u003e\u003cp\u003eMỗi dòng tiếp theo $$$q$$$ chứa $$$2$$$ số nguyên $$$l$$$ và $$$r$$$ ($$$1 \\le l \\le r \\le n$$$)\u0026nbsp;— các điểm cuối của khoảng truy vấn này.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eĐối với mỗi truy vấn, in câu trả lời của nó trên một dòng mới.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e6 3\n2 3 10 7 5 14\n1 6\n2 4\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eTruy vấn đầu tiên hỏi về toàn bộ mảng. Bạn có thể phân chia nó thành $$$[2]$$$, $$$[3,10,7]$$$, và $$$[5,14]$$$. Khoảng con đầu tiên có tích và LCM bằng $$$2$$$. Khoảng thứ hai có tích và LCM bằng $$$210$$$. Và khoảng thứ ba có tích và LCM bằng $$$70$$$. Một phân chia khả thi khác là $$$[2,3]$$$, $$$[10,7]$$$, và $$$[5,14]$$$.\u003c/p\u003e\u003cp\u003eTruy vấn thứ hai hỏi về khoảng $$$(2,4)$$$. Tích của nó bằng với LCM của nó, vì vậy bạn không cần phải phân chia thêm.\u003c/p\u003e\u003cp\u003eTruy vấn cuối cùng hỏi về khoảng $$$(3,5)$$$. Bạn có thể phân chia nó thành $$$[10,7]$$$ và $$$[5]$$$.\u003c/p\u003e"}}]}