Description

给定区间[L,R]，请统计有多少对整数A,B(L<=A,B<=R)满足A xor B的值在二进制表示下，去掉所有前导0后是回文串

Format

Input

第一行包含一个正整数T(1<=T<=100)，表示测试数据的组数。

每组数据包含一行两个整数L,R(0<=L<=R<=10^12)，含义如题面所述。

Output

对于每组数据输出一行一个整数，即满足条件的整数对个数。

Samples

3
1 4
0 0
4 8

12
1
15