1443: 奇妙变换
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：4
题目描述
【问题描述】
为了奖励牛牛同学帮妈妈解决了大写中文数字的问题，牛牛妈妈特地抽出一个周末的时间带着牛牛来到梦幻儿童乐园游玩。
在游乐园，牛牛看到了一个非常有意思的游戏：游戏一开始，电脑屏幕上只有一个序列“A”，而后的每一次变化都把序列中的“A”变成“AB”，“B”变成“A”。游戏一直继续……，最后屏幕上得到了序列“ABAABABAABAABABAABA……”。当然更有意思的是，电脑会提出Q个询问，每次询问：在第m个字符和第n个字符之间有多少个“A”（包括第m、n个字符在内）。
你能帮牛牛解决这个问题吗？
【输入格式】
第一行为一个整数Q，后面有Q行，每行两个数用空格隔开的整数m，n。
【输出格式】
共Q行，每行一个回答。
【样例输入】
1
2 8
【样例输出】
4
【数据范围】
1≤Q≤5000
1≤m≤n≤263
保证每次询问时，所询问的区间已经生成。
样例输入 复制
1
2 8
样例输出 复制
4