{"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\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eСмале се борел со една колонија на мравки, која се состоела од $n$ мравки, подредени во една редица. Секоја мравка $i (1 \\leq i \\leq n)$ имала моќ $s_i$.\u003c/p\u003e\n\u003cp\u003eСмале ќе одбере два броеви $l$ и $r$ ($ 1\\leq l \\leq r \\leq n$) и секој пар од мравки помеѓу $l$ и $r$ ќе се борат помеѓу себе. Кога две мравки $i$ и $j$ се борат, мравката $ј$ добива еден поен ако и само акo $s_i$ е делител на $s_j$(исто така, мравката $i$ добива еден поен ако $s_j$ е делител на $s_i$.\u003c/p\u003e\n\u003cp\u003eКога сите борби завршиле, Смале ги рангирал мравките. Мравката $i$, со $v_i$ поени ќе биде ослободена ако и само ако $v_i \u003d r-l$, или со други зборови, ако мравката освоила поен во секоја од борбите во која учествувала. После тоа, Смале ќе ги убие останатите мравки. Забележете дека може да има многу мравки кои ќе бидат ослободени или да нема ниту една ослободена мравка.\u003c/p\u003e\n\u003cp\u003eБидејќи Смале знае дека вие сте бистри програмери, тој ви дал $t$ различни сегменти $[l_i,r_i]$ и бара од вас да му кажете колку мравки ќе бидат убиени, односно колку мравки нема да бидат ослободени ако се борам само мравките во опсегот.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eПрвата линија содржи еден цел број $n$ ($1 \\leq n \\leq 10^5$) - големината на колонијата.\u003c/p\u003e\n\u003cp\u003eВтората линија содржи $n$ цели броеви, ($s_1, s_2, \\ldots, s_n$ ($1 \\leq s_i \\leq 10^9$) - моќноста на секоја мравка.\u003c/p\u003e\n\u003cp\u003eТретата линија содржи еден цел број $t$ ($1 \\leq t \\leq 10^5$) - бројот на прашанки.\u003c/p\u003e\n\u003cp\u003eСекоја од следните $t$ линии содржи два цели броеви $l_i$ и $r_i$ ($1\\leq l_i \\leq r_i \\leq n$) - опсегот на мравки кои ќе учествуваат во борбата.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eИспечатете $t$ линии. $i$-тата линија треба да го содржи бројот на мравки кои нема да бидат ослободени, ако се борат мравките кои влегуваат во сегментот $[l_i, r_i]$.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eВлез\u003c/th\u003e\n \u003cth\u003eИзлез\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1 3 2 4 2\n4\n1 5\n2 5\n3 5\n4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n4\n1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eВо првата борба, поените на секоја мравка се $v \u003d [4, 0, 2, 0, 2]$, мравката со индекс $1$ е ослободена, односно има $4$ мравки кои не се ослободени.\u003c/p\u003e\n\u003cp\u003eВо втората борба, поените се $v \u003d [0, 2, 0, 2]$, па нема ниту една ослободен мравка.\u003c/p\u003e\n\u003cp\u003eВо третата борба, поените се $v \u003d [2, 0, 2]$, па мравите $3$ и $5$ се ослободени, односно една мравка не е ослободена.\u003c/p\u003e\n\u003cp\u003eВо четвртата борба, поените се $v \u003d [0, 1]$, па има само една мравка која не е ослободена.\u003c/p\u003e"}}]}