RAW and FBI have received an encrypted message having probable key between numbers L and R (both inclusive). FBI claims that the required key is the number which is prime where as the RAW claims that the required key is a number whose total number of factors is a prime number. But the MI-6 claims that the total probable keys are the ones which are claimed by FBI & RAW both as well as the keys which are claimed by neither FBI nor RAW. Can you count the number of keys MI-6 claims?

INPUT:
The first line of input contains the number of test cases T. T lines follow. Each line contains two space separated integers L and R.

OUTPUT:
For each test case output the number of probable keys claimed by MI-6 on new line.

CONSTRAINTS:

• 1<=T<=50000

• 1 < L<=R <=10¹²