Yash taught his students some tricks about math in his last session. In his next session he ask them a question related to that to check who had learned the topic properly. Question is :

You are given Q queries. each query is of form [L,R]. Your task is to find xor of greatest odd divisor of each number in that range.

You being one of the Yash's obedient students have learned this topic properly and to prove that you need to answer this question as quickly as possible. Can you prove your worth?

Input

The first line contains only one integer Q denoting number of queries.

Next Q line contains two space separated integers, L and R denoting each query.

Output

Print one integer for each query denoting xor of greatest odd divisor for each number in given range.

Constraints

1 <= Q <= 10^5

1 <= L <= R <= 10^6