Description

给定区间[l,r]，你需要求出[l,r]中因子个数小于等于4的正整数个数。

Format

Input

本题包含多组测试数据。

第一行给出一个整数T(1≤T≤100000)，表示测试数据的组数。

接下来有T行,每行给出两个正整数l,r(1≤l≤r≤1000000)，具体意义如题目所示。

Output

输出T行，每行1个整数，其中第i个数表示第i个数据的答案。

Samples

1
1 6
1 100

6
62

Hint

不出