{"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\u003e这次,Baby Ehab只会切割而不会粘贴。他从一张纸上开始,上面写着一个长度为$$$a$$$的数组。然后他做以下操作:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e他选择一个范围$$$(l, r)$$$,剪切出子段$$$a_l, a_{l + 1}, \\ldots, a_r$$$,移除其余的数组。\u003c/li\u003e\n\u003cli\u003e然后他将这个范围切割成多个子范围。\u003c/li\u003e\n\u003cli\u003e为了增添一些数论的趣味,他要求每个子范围的元素的乘积等于它们的\u003ca href\u003d\"https://zh.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E5%85%AC%E7%BA%A6%E5%80%BC\"\u003e最小公倍数(LCM)\u003c/a\u003e。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e形式上,他将$$$a_l, a_{l + 1}, \\ldots, a_r$$$的元素划分为连续的子数组,使得每个子数组的乘积等于其LCM。现在,对于$$$q$$$个独立范围$$$(l, r)$$$,告诉Baby Ehab他需要的最小子数组数目。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含$$$2$$$个整数$$$n$$$和$$$q$$$($$$1 \\le n,q \\le 10^5$$$)— 数组$$$a$$$的长度和查询数。\u003c/p\u003e\n\u003cp\u003e接下来一行包含$$$n$$$个整数$$$a_1$$$,$$$a_2$$$,$$$\\ldots$$$,$$$a_n$$$($$$1 \\le a_i \\le 10^5$$$)— 数组$$$a$$$的元素。\u003c/p\u003e\n\u003cp\u003e接下来的每一行包含$$$q$$$个整数$$$2$$$和$$$l$$$($$$1 \\le l \\le r \\le n$$$)— 这个查询区间的端点。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个查询,在新的一行上打印其答案。\u003c/p\u003e"}},{"title":"例子","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":"注意","value":{"format":"HTML","content":"\u003cp\u003e第一个查询询问整个数组。你可以将其划分为$$$[2]$$$,$$$[3,10,7]$$$和$$$[5,14]$$$。第一个子范围的乘积和LCM等于$$$2$$$。第二个子范围的乘积和LCM等于$$$210$$$。第三个子范围的乘积和LCM等于$$$70$$$。另一种可能的划分是$$$[2,3]$$$,$$$[10,7]$$$和$$$[5,14]$$$。\u003c/p\u003e\n\u003cp\u003e第二个查询询问范围$$$(2,4)$$$。其乘积等于其LCM,因此无需进一步划分。\u003c/p\u003e\n\u003cp\u003e最后一个查询询问范围$$$(3,5)$$$。你可以将其划分为$$$[10,7]$$$和$$$[5]$$$。\u003c/p\u003e"}}]}