题目描述

为了奖励牛牛同学帮妈妈解决了大写中文数字的问题，牛牛妈妈特地抽出一个周末的时间带着牛牛来到梦幻儿童乐园游玩。 在游乐园，牛牛看到了一个非常有意思的游戏：游戏一开始，电脑屏幕上只有一个序列“A”，而后的每一次变化都把序列中的“A”变成“AB”，“B”变成“A”。游戏一直继续……，最后屏幕上得到了序列“ABAABABAABAABABAABA……”。当然更有意思的是，电脑会提出Q个询问，每次询问：在第m个字符和第n个字符之间有多少个“A”（包括第m、n个字符在内）。 你能帮牛牛解决这个问题吗？

输入格式

第一行为一个整数 $Q$，后面有 $Q$ 行，每行两个数用空格隔开的整数 $m，n$ 。

输出格式

共 $Q$ 行，每行一个回答。

样例

输入#1

1
2 8

输出#1

4

数据范围

$1≤Q≤5000$ $1≤m≤n≤2^{63}$

现在是知道这个和斐波那契有一样的规律，但是m,n的范围太大了， 不知道该怎么处理。 题目链接：https://oj.nbdp.net/problem.php?id=4795