注意

本题版权归 所有。

题目来源：https://www.luogu.com.cn/problem/T739397

题目在导入时有改动。

题目描述

称正整数 $N$ 是「七巧板数」，当且仅当存在一组多边形，满足：

1. 这些多边形可以拼成 $N \times 1$ 的长方形。
2. 这些多边形可以拼成正方形。
3. 拼接两个图形时，所有多边形的所有顶点都是格点，且都至少有一条边平行于坐标轴。

给定 $q$ 个询问，每次给定一个区间 $[l, r] \subseteq [1, n]$，求区间内所有「七巧板数」的和。

输入格式

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

下面 $q$ 行，每行两个正整数 $l, r$。

输出格式

对于每个询问，输出一行一个非负整数表示答案。

样例

10 10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

1
2
0
4
5
0
0
8
9
10

数据范围

对于 $50\%$ 的数据，保证 $q = n$，且第 $i$ 个询问中 $l = r = i$。

对于 $100\%$ 的数据，$1 \le l \le r \le n \le 10^{10}$，$1 \le q \le 10^5$。

本题共有 $10$ 个测试点，对于第 $i$ 个测试点，$n = 10^i$。