まず、頂点 \(L\) から頂点 \(R\) までの \(R-L+1\) 頂点あるグラフを考えます。\(L\le i < j \le R\) に対し、\(\operatorname{popcount}(i) < \operatorname{popcount}(j)\) を満たす場合に頂点 \(i\) から頂点 \(j\) へ有向辺を繋ぐことを考えます。このグラフは DAG となり、さらに頂点 \(i\) から頂点 \(j\) へ、頂点 \(j\) から頂点 \(k\) へ有向辺がある場合必ず頂点 \(i\) から頂点 \(k\) へも有向辺が存在します（すなわち、推移律が成り立ちます）。したがって、Dilworth の定理よりこのグラフにおいて最小パス被覆の大きさと最大反鎖の大きさは一致します。

このグラフにおける最小パス被覆の大きさは本問題の答えであるため、本問題の答えは以下の問題の答えと一致します：

以下の条件を全て満たす整数列 \(x=(x_1,x_2,\ldots,x_n)\) の長さの最大値を求めよ：

• \(L\le x_1 < x_2 < \dots < x_n \le R\)
• \(\operatorname{popcount}(x_1) \geq \operatorname{popcount}(x_2) \geq \dots \geq \operatorname{popcount}(x_n)\)

以降はこの問題の答えを求めることを考えます。

まず、以下の補題について考えます：

非負整数 \(m,l,r\) に対し、以下の条件を全て満たす整数列 \(x=(x_1,x_2,\ldots,x_n)\) の長さの最大値は \(\displaystyle \max_{l\le k\le r}\binom mk\) と一致する。また、最大値は \(\displaystyle \binom mk\) を最大とする \(l\le k\le r\) に対し、\(\operatorname{popcount}\) が \(k\) である値を昇順に並べることで達成できる。

• \(0\le x_1 < x_2 < \dots < x_n < 2^m\)
• \(r\geq \operatorname{popcount}(x_1) \geq \operatorname{popcount}(x_2) \geq \dots \geq \operatorname{popcount}(x_n)\geq l\)

証明：

\(S\) を \(0\) 以上 \(2^m\) 未満で \(\operatorname{popcount}\) が \(l\) 以上 \(r\) 以下である整数の集合とします。

\(S\) 内の要素に対し、整数同士の包含関係を bit の包含関係で定義します。すると、整数列 \(x\) が条件を満たすならば \(x\) を集合として見たものは反鎖となります。したがって、LYM 不等式より \(\displaystyle \sum_{i=1}^n\binom{m}{\operatorname{popcount}(x_i)}^{-1}\le 1\) が成立します。

\(l\le \operatorname{popcount}(x_i)\le r\) より、\(\displaystyle M=\max_{l\le k\le r}\binom mk\) に対し \(\displaystyle 1\geq\sum_{i=1}^n\binom{m}{\operatorname{popcount}(x_i)}^{-1}\geq \frac nM\) となることから \(n\le M\) が従います。そして、\(\displaystyle \binom mk\) を最大とする \(l\le k\le r\) に対し \(\operatorname{popcount}\) が \(k\) である値を昇順に並べることで \(n=M\) とすることが可能です。

与えられた整数 \(L,R\) に対し、以下を満たす整数列 \(T=(T_0,T_1,\ldots,T_N)\) が存在します：

• \(L=T_0 < T_1<\dots < T_N=R+1\)
• \(i=0,1,\ldots,N-1\) に対し \(T_{i+1}-T_i\) はある非負整数 \(c_i\) を用いて \(2^{c_i}\) と表され、さらに \(T_i\) は \(2^{c_i}\) の倍数である。
• \(N=O(\log R)\)

このように区間 \([L,R]\) を分割すると、各区間 \([T_i,T_{i+1})\) では上で示した補題より \(\operatorname{popcount}\) が同じ値を全て取る操作が最適です。したがって、\(d[i][j]\) を「\(T_i\) 未満の要素を考えた時に、最後の要素の \(\operatorname{popcount}\) が \(j\) 以上である場合の \(x\) の長さの最大値」とした動的計画法を用いて答えを計算することができます。計算量は \(O(\log^2R)\) です。

LYM 不等式などに関しては次の記事を参照してください：Sperner の定理 - AtCoderInfo

実装例(Python3)

import sys

input = sys.stdin.readline
C = [[0] * 62 for _ in range(62)]
for i in range(62):
    C[i][0] = C[i][i] = 1
    for j in range(1, i):
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
for _ in range(int(input())):
    l, r = map(int, input().split())
    r += 1
    d = [0] * 62
    while l < r:
        x = min(1 << ((r - l).bit_length() - 1), l & -l)
        c = x.bit_length() - 1
        p = l.bit_count()
        for i in range(c + 1):
            d[p + i] += C[c][i]
        for i in range(60, -1, -1):
            d[i] = max(d[i], d[i + 1])
        l += x
    print(d[0])