{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e Long long ago, there was an ancient rabbit kingdom in the forest. Every rabbit in this kingdom was not cute but totally pugnacious, so the kingdom was in chaos in season and out of season.\u003cbr\u003e n rabbits were numbered form 1 to n. All rabbits\u0027 weight is an integer. For some unknown reason, two rabbits would fight each other if and only if their weight is NOT co-prime.\u003cbr\u003e Now the king had arranged the n rabbits in a line ordered by their numbers. The king planned to send some rabbits into prison. He wanted to know that, if he sent all rabbits between the i-th one and the j-th one(including the i-th one and the j-th one) into prison, how many rabbits in the prison would not fight with others.\u003cbr\u003e Please note that a rabbit would not fight with himself.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" The input consists of several test cases.\u003cbr\u003e The first line of each test case contains two integer n, m, indicating the number of rabbits and the queries.\u003cbr\u003e The following line contains n integers, and the i-th integer W\u003csub\u003ei\u003c/sub\u003e indicates the weight of the i-th rabbit.\u003cbr\u003e Then m lines follow. Each line represents a query. It contains two integers L and R, meaning the king wanted to ask about the situation that if he sent all rabbits from the L-th one to the R-th one into prison.\u003cbr\u003e (1 \u0026lt;\u003d n, m, W\u003csub\u003ei\u003c/sub\u003e \u0026lt;\u003d 200000, 1 \u0026lt;\u003d L \u0026lt;\u003d R \u0026lt;\u003d n)\u003cbr\u003e The input ends with n \u003d 0 and m \u003d 0.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":" For every query, output one line indicating the answer."}},{"title":"Sample","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\u003e3 2\r\n2 1 4\r\n1 2\r\n1 3\r\n6 4\r\n3 6 1 2 5 3\r\n1 3\r\n4 6\r\n4 4\r\n2 6\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1\r\n1\r\n3\r\n1\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e In the second case, the answer of the 4-th query is 2, because only 1 and 5 is co-prime with other numbers in the interval [2,6] .\u003cbr\u003e"}}]}