seuOJ472 - 配对

题目描述

定义两个正整数 x,yx,y 是配对的，当且仅当 x⊕y>min⁡(x,y)x\oplus y > \min(x,y) ，其中 ⊕\oplus 代表按位异或。

我们使用符号 p(x,y)p(x,y) 代表 x,yx,y 之间是否配对，换句话来说，如果 x,yx,y 之间配对，那么 p(x,y)=1p(x,y)=1，否则 p(x,y)=0p(x,y)=0。

给定 l,rl,r，求 ∑x=lr∑y=xrp(x,y)\sum_{x=l}^r \sum_{y=x}^r p(x,y)。

按位异或运算是一种二进制运算方法，用符号 ⊕\oplus 表示。对两个二进制数进行按位异或运算，规则是如果相应位上的两个数字相同则结果为 00 ，如果相应位上的两个数字不同则结果为 11。 例如，假设有两个二进制数 A=1100A = 1100 和 B=1010B = 1010，进行按位异或运算的结果如下：

  A = 1100
  B = 1010
  ————按位异或运算
  R = 0110

也就是说，AA 和 BB 的第一位都是 11，所以结果的第一位为 00；AA 的第二位为 11，BB 的第二位为 00，所以结果的第二位为 11；以此类推，可以得到最后的结果 R=0110R = 0110。

Thank you, ChatGPT, for introducing us to bitwise XOR operation.

输入格式

第一行，一个整数 t(1≤t≤105)t(1\le t \le 10^5)，代表询问组数。
接下来连续的 tt 行，每行两个整数 l,r(1≤l≤r≤109)l,r(1\le l \le r\le 10^9)，含义如题目描述所示。

输出格式

对于每组输出，输出一行整数代表 ∑x=lr∑y=xrp(x,y)\sum_{x=l}^r \sum_{y=x}^r p(x,y) 的值。

样例

输入样例

3
1 3
2 7
11 62

输出样例

2
8
731