Description

对于一个数若满足
1.它是奇数
2.它所有的因子都是奇数
3.它因子的个数是奇数
则称这个数是超级奇数（Super Odd Number）。

Input

输入一个数n代表有n组测试数据（1<=n<=10000）
每组测试数据包含两个数A，B（1<=A<=B<=100000）。

Output

对于每组测试数据输出区间[A,B]内有多少个超级奇数（区间包括A与B）。

Sample Input

2
9089 30816
14010 18744

Sample Output

40
9

HINT

Source

NBU OJ