AT_abc476_g [ABC476G] Increasing Popcount

$ L\le R $ を満たす正整数 $ L,R $ が与えられます。 以下の条件を満たす長さ $ R-L+1 $ の正整数列 $ A=(A_L,A_{L+1},\ldots,A_R) $ を**良い整数列**と呼びます： - $ L\le i < j\le R $ を満たすすべての整数の組 $ (i,j) $ に対し、 $ A_i = A_j $ ならば $ \operatorname{popcount}(i)

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ L $ $ R $

$ T $ 行出力せよ。 $ i $ 行目 $ (1\le i\le T) $ には、 $ i $ 番目のテストケース $ \text{case}_i $ に対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 $ (A_3,A_4,A_5,A_6)=(1,2,2,3) $ は良い整数列で、 $ \max(A_3,A_4,A_5,A_6)=3 $ となります。 $ \max(A_3,A_4,A_5,A_6) < 3 $ を満たす良い整数列は存在しないので、 $ 1 $ 行目には $ 3 $ を出力してください。 ### Constraints - $ 1\le T\le 10^4 $ - $ 1\le L \le R\le 10^{18} $ - 入力される値は全て整数