【CodeForces - 485C】Bits （二进制相关，数学，贪心）

题干：

Let's denote as  the number of bits set ('1' bits) in the binary representation of the non-negative integer x.

You are given multiple queries consisting of pairs of integers l and r. For each query, find the x, such that l ≤ x ≤ r, and  is maximum possible. If there are multiple such numbers find the smallest of them.

Input

The first line contains integer n — the number of queries (1 ≤ n ≤ 10000).

Each of the following n lines contain two integers li, ri — the arguments for the corresponding query (0 ≤ li ≤ ri ≤ 1018).

Output

For each query print the answer in a separate line.

Examples

Input

3
1 2
2 4
1 10

Output

1
3
7

Note

The binary representations of numbers from 1 to 10 are listed below:

题目大意：

我们定义表示数x在二进制表示下所有数位中1的个数。

现在给定两个整数 l 和r。希望找到一个 x，满足 l ≤ x ≤ r，并且的值最大。如果有多种方案输出最小的一种。

解题报告：

   贪心处理，并且他这个：If there are multiple such numbers find the smallest of them.也给了提示，需要从小到大贪心。对于这个题我们不需要首先关注这个值是多少，而是关注值中有多少个1（因为首先输出1最多的数字）。我们可以采用上下界贪心的思路，最小的值肯定是 l ，答案肯定不会少于l，并且答案首先最少就是popcount( l )，然后我们依次增加答案并且保证构造的是最小值，怎么做到呢？就是从低位到高位按位增加一个1。依次类推 就完事了。注意写法。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
int n,x,y,a[MAX],ans;
int main() 
{
	ll n,l,r;
	cin>>n;
	while(n--) {
		scanf("%lld%lld",&l,&r);
		ll ans = 0;
		ll bit = 1;
		while(l<=r) {
			ans = l;
			l |= bit;
			bit<<=1;
		}
		printf("%lld\n",ans);
	} 
	return 0;
}