{"trustable":false,"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":"MD","content":"### Description\n\nYou are given an array $A$ containing $N$ integers (indexed from $1$ to $N$).\n\nDefine a *score* of array $a$ containing $n$ integers (indexed from $1$ to $n$) as the minimum number of partitions such that every partition must have their product equal to their Least Common Multiple (LCM).\n\nSuppose that array $a$ is splitted into $k$ partitions (numbered from $1$ to $k$). Partition $i$ is a subarray $a_{l_i}, a_{l_i+1}, \\dots, a_{r_i}$. The partitions must satisfy the following requirements: $l_i \\leq r_i$ for $1 \\leq i \\leq k$; $l_1 \u003d 1$; $r_k \u003d n$; and $r_i + 1 \u003d l_{i+1}$ for $1 \\leq i \u003c k$. For example, array $a \u003d [2, 3, 10, 7, 5, 14]$ can be splitted into $3$ partitions: $[2]$, $[3, 10, 7]$, and $[5, 14]$.\n\nYou are asked $Q$ independent queries (numbered from $1$ to $Q$). In query $i$, given two integers $L_i$ and $R_i$; determine the score of subarray $A_{L_i}, A_{L_i+1}, \\dots, A_{R_i}$.\n\n### Constraints\n\n- $1 \\leq N, Q \\leq 100 \\, 000$\n- $1 \\leq A_i \\leq 100 \\, 000$ for $1 \\leq i \\leq N$.\n- $1 \\leq L_i \\leq R_i \\leq N$ for $1 \\leq i \\leq Q$.\n\n### Input\n\n\u003cpre\u003e\nN Q\nA\u003csub\u003e1\u003c/sub\u003e A\u003csub\u003e2\u003c/sub\u003e … A\u003csub\u003eN\u003c/sub\u003e\nL\u003csub\u003e1\u003c/sub\u003e R\u003csub\u003e1\u003c/sub\u003e\nL\u003csub\u003e2\u003c/sub\u003e R\u003csub\u003e2\u003c/sub\u003e\n⋮\nL\u003csub\u003eQ\u003c/sub\u003e R\u003csub\u003eQ\u003c/sub\u003e\n\u003c/pre\u003e\n\n### Output\n\nFor each query, output in a single line, the score of the asked subarray.\n\n### Sample Input 1\n\n\u003cpre\u003e\n6 3\n2 3 10 7 5 14\n1 6\n2 4\n3 5\n\u003c/pre\u003e\n\n### Sample Output 1\n\n\u003cpre\u003e\n3\n1\n2\n\u003c/pre\u003e\n\n### Explanation\n\nThe first query asks the score of the whole array. You can partition it into $[2]$, $[3, 10, 7]$ and $[5, 14]$. Another possible partition is $[2, 3]$, $[10, 7]$, and $[5, 14]$.\n\nThe second query asks the score of array $[3, 10, 7]$. Its product is already equal to its LCM.\n\nThe third query asks the score of array $[7, 5, 14]$. You can partition it into $[10, 7]$ and $[5]$."}}]}