小 X 是一位热爱数学的男孩子，在茫茫的数字中，他对质数更有一种独特的情感。小 X 认为，质数是一切自然数起源的地方。

在小 X 的认知里，质数是除了本身和 1 以外，没有其他因数的数字。

但由于小 X 对质数的热爱超乎寻常，所以小 X 同样喜欢那些虽然不是质数，但却是由两个质数相乘得来的数。

于是，我们定义，一个数是小 X 喜欢的数，当且仅当其是一个质数，或是两个质数的乘积。

而现在，小 X 想要知道，在 L 到 R 之间，有多少数是他喜欢的数呢？

第一行输入一个正整数 Q，表示询问的组数。

接下来 Q 行。包含两个正整数 L 和 R。保证 L≤R。

输出 Q 行，每行一个整数，表示小 X 喜欢的数的个数。