You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

注意：这 不 是 数位&*!@#(dp)!#模?>.\版*题!@$=@。

题目描述

对于一个正整数 $n$，令 $n$ 在二进制下从最低位到最高位的数位依次为 $n_0, n_1, \dots, n_k$，例如，若 $n = 11$，则 $k = 3$，$n_0 = 1, n_1 = 1, n_2 = 0, n_3 = 1$。

让 $n$ 的 权值 $f(n)$ 表示为 $\sum\limits_{i=0}^k [i \bmod 2 = 1]n_i - \sum\limits_{i=0}^k [i \bmod 2 = 0]n_i$。对于一个正整数 $n$，它被称作是 好的 当且仅当 $\lvert f(n) \rvert$ 是 $3$ 的倍数。

给出 $L, R$，请你求出满足 $L \leq n \leq R$ 的 好的 $n$ 的个数。

输入格式

本题单个测试点内有多组数据。

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行两个整数 $L, R$ 描述一组数据。

输出格式

共 $T$ 行，每行一个整数表示答案。

样例

1
4 7

1

样例解释

在 $[4, 7]$ 之间的数中只有 $6$ 满足 $\lvert f(n) \rvert = 0$ 是 $3$ 的倍数。

数据规模与约定

本题采用捆绑测试。

• Subtask 0（13 pts）：$R \leq 10$。
• Subtask 1（20 pts）：$R \leq 3\times 10^3$。
• Subtask 2（20 pts）：$R \leq 5\times 10^5$。
• Subtask 3（47 pts）：无特殊限制。

对于所有数据，$1 \leq L \leq R \leq 10^{18}$，$1 \leq T \leq 2\times 10^4$。