题目描述

一个很长的二进制字符串通过以下过程生成：

1. 从字符串 $\tt{1}$ 开始。
2. 每一秒，我们将当前字符串中的每个 $\tt{1}$ 替换为 $\tt{10}$，并将每个 $\tt{0}$ 替换为 $\tt{1}$。

前几秒字符串的状态如下： $1, 10, 101, 10110, 10110101$。

令 $s$ 为这个过程执行了 $10^{100}$ 秒后得到的字符串。你需要回答 $Q$ 个如下形式的查询： $s$ 中从第 $l$ 个字符到第 $r$ 个字符（包含两端）之间有多少个 $1$？

输入格式

第一行包含一个整数 $Q$ （$1 \le Q \le 300\,000$），表示查询的数量。

接下来的 $Q$ 行，每行包含两个以空格分隔的整数 $l, r$ （$1 \le l \le r \le 10^{18}$），代表查询。

输出格式

对于每个查询，输出 $s$ 中从第 $l$ 个字符到第 $r$ 个字符（包含两端）之间 $1$ 的个数。

3
3 9
6 6
1 12

5
1
8

提示

注释

可以证明，该字符串的前 $12$ 个字符是 $101101011011$。

对于第一个查询，第 $3$ 个字符到第 $9$ 个字符之间有 $5$ 个 1，相关的子串是 $1101011$。

对于第二个查询，第 $6$ 个字符到第 $6$ 个字符之间有 $1$ 个 1，相关的子串是 $1$。

对于第三个查询，第 $1$ 个字符到第 $12$ 个字符之间有 $8$ 个 1，相关的子串是 $101101011011$。

计分

子任务 $1$ （$7$ 分）： $Q = 1$， $r \le 300\,000$

子任务 $2$ （$10$ 分）： $l = 1$， $r \le 300\,000$

子任务 $3$ （$13$ 分）： $r \le 300\,000$

子任务 $4$ （$20$ 分）： $l=1$， $r$ 等于某个整数秒后字符串的长度

子任务 $5$ （$15$ 分）： $l=r$

子任务 $6$ （$15$ 分）： $Q = 1$

子任务 $7$ （$10$ 分）： $r \le 10^9$

子任务 $8$ （$10$ 分）： 无额外限制

翻译由 DeepSeek 完成