小红定义了一个函数 表示所有严格小于 的 的因子之和，例如 。 小红认为一个数字 是好数，当且仅当 是一个偶数（ 表示乘法），例如 就是好数，因为 ，是偶数，当然 也是好数。 现在小苯有一个数组 ，小红提出了 次询问 ，每次她都想知道 这些数字中有多少个好数，请你帮她算一算吧。

输入描述:

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

输出描述:

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