小苯的好数

题号：NC287463
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红定义了一个函数 $f(x)$ 表示所有严格小于 $x$ 的 $x$ 的因子之和，例如 $f(6)=1+2+3=6$ 。
小红认为一个数字 $x$ 是好数，当且仅当 $x \cdot f(x)$ 是一个偶数（ $\cdot$ 表示乘法），例如 $4$ 就是好数，因为 $4 \times f(4)=4 \times (1+2)=12$ ，是偶数，当然 $6$ 也是好数。

现在小苯有一个数组 $a$ ，小红提出了 $q$ 次询问 $l, r\ (1 \leq l \leq r \leq n)$ ，每次她都想知道 $a_l, a_{l+1},\dots,a_r$ 这些数字中有多少个好数，请你帮她算一算吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行两个正整数 ，分别表示小苯的数组长度，以及小红的提问次数。
第二行  个正整数 ，表示  数组。
接下来  行，每行两个正整数 ，表示小红每次询问的区间。

输出描述:

对于每组测试数据：
输出  行，每行单独一个整数，表示当前询问的答案。

示例1

输入

复制

1
6 3
2 3 4 5 6 9
1 3
2 5
1 6

输出

复制

2
2
4

说明

 都是好数。