A long binary string is formed via the following process:
Start with the string .
Every second, we replace each of the current string with and each of the current string with .
The state of the string in the first few seconds is as follows: .
Let be the string obtained at the end of the process after running it for seconds. You want to answer queries of the following type: how many ones are there between the -th character and -th character (inclusive) of ?
输入格式
The first line contains a single integer (), denoting the number of queries.
The next lines each contain two space-separated integers (), representing the queries.
输出格式
For each query, output the number of ones between the -th character and -th character (inclusive) of .
样例
样例输入 1
3
3 9
6 6
1 12
样例输出 1
5
1
8
数据范围与提示
Note
One can show that the first characters of the string are .
For the first query, there are ones between the 3rd character and 9th character. The relevant substring is .
For the second query, there is one between the 6th character and 6th character. The relevant substring is .
For the third query, there are ones between the 1st character and 12th character. The relevant substring is .
Scoring
Subtask ( points): ,
Subtask ( points): ,
Subtask ( points):
Subtask ( points): , is equal to the length of the string after some integer number of seconds.
