门牌灯带

一排门牌的编号为 $1,2,\ldots,n$。如果一个编号的不同质因数个数恰好为 $2$，这盏门牌灯会亮起。

例如 $12=2^2\cdot 3$，不同质因数为 $2$ 和 $3$，因此编号 $12$ 的门牌灯会亮起。

现在有 $q$ 次询问。每次给出区间 $[l,r]$，请输出编号在该区间内会亮起的门牌数量。

第一行两个整数 $n,q$。

接下来 $q$ 行，每行两个整数 $l,r$，表示一次询问。

输出 $q$ 行。对于每次询问，输出一个整数，表示区间 $[l,r]$ 内会亮起的门牌数量。

$1 \le n \le 2\cdot 10^6$。

$1 \le q \le 2\cdot 10^5$。

$1 \le l \le r \le n$。