luogu#P8567. [JRKSJ R6] Nothing

[JRKSJ R6] Nothing

题目背景

【此处应有图】

题目描述

我们定义 f(x)f(x) 表示 xx22 进制下最低的 11 的位置(你需要注意,二进制下的最低位是第 00 位)。以下是其在 C++ 语言中的代码(未考虑数据类型造成的问题):

int f(int x){
	int ans = 0;
	while (x % 2 == 0){
		x /= 2;
		ans += 1;
	}
	return ans;
}

共有 TT 组询问,每组询问给定区间 [l,r][l,r],求有多少个 i[l,r]i\in [l,r] 使得 f(i)<f(i+1)f(i)< f(i+1)

输入格式

第一行一个正整数 TT
接下来 TT 行每行两个正整数 l,rl,r 表示一次询问。

输出格式

TT 行每行一个整数表示答案。

2
3 5
15 20
2
3

提示

数据规模

本题采用捆绑测试。

Subtask\text{Subtask} TT\le 特殊限制 Score\text{Score}
11 10510^5 l=rl=r 1010
22 10410^4 rl103r-l\le10^3 3030
33 10510^5 r106r\le10^6 2020
44 4040

对于 100%100\% 的数据,1T1051\le T\le 10^51lr10181\le l\le r\le 10^{18}