U403634 糊纸

定义 $f(x_1,\cdots,x_m)$ 表示有多少对 $(i,j)(1\le i\le j\le m)$ 满足 $x_i,\cdots,x_j$ 两两互质（只有一个数也认为其两两互质）。 给定 $n(n\le 5\times 10^5)$ 个正整数 $a_1,a_2,\cdots,a_n(a_i\le 5\times 10^5)$，有 $q(q\le 5\times 10^5)$ 次询问，每次询问给出 $l,r$，求 $f(a_l,\cdots,a_{r})$。

第一行两个正整数 $n,q(n,q\le 5\times 10^5)$。 接下来一行 $n$ 个正整数，依次表示 $a_1,\cdots,a_n(a_i\le 5\times 10^5)$。 接下来 $q$ 行每行两个正整数 $l,r(1\le l\le r\le n)$。

$q$ 行，每行一个正整数表示答案。

样例 $1$ 中，第一组询问符合条件的 $(i,j)$ 有 $(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,3),(4,5),(1,3)$ 共 $9$ 个，第二组询问符合条件的 $(i,j)$ 有 $(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(1,3)$ 共 $7$ 个。 对于前 $20\%$ 的数据，$n,q\le 100$，$a_i\le 10$。 对于另外 $20\%$ 的数据，$q=1$。 对于 $100\%$ 的数据，$n,q,a_i\le 5\times 10^5$。