Read problems statements in  Mandarin Chinese  and  Russian. 
Chef doesn't love math anymore. He loves Sasha. Sashen'ka is cute.

Chef goes on a date with her. Flowers are boring, while numbers are not. He knows that most of all this girl loves numbers, that's why he is going to bring ribbon with numbers L, L+1, L+2, ..., R written on it.

Sasha thinks that numbers with prime number of divisors are special. That's why she is going to kiss boy for each such number he will bring.

Now Chef wonder how many times he will be kissed by Sashen'ka ?

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two number L, R.
 
------ Output ------ 

For each test case, output a single line containing answer for corresponding test case.
 
------ Constraints ------ 

$1 ≤ T ≤ 5$
$1 ≤ L ≤ R ≤ 10^{12}$
$0 ≤ R-L ≤ 10^{6}$
 
----- Sample Input 1 ------ 
1
1 10
----- Sample Output 1 ------ 
6
----- explanation 1 ------ 
Example case 1. Numbers 2,3,4,5,7,9 are special.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics


Solutions:
from bisect import bisect
from math import sqrt, floor
prime = []
isprime = [True] * (10 ** 6 + 2)
isprime[0] = False
isprime[1] = False
for x in range(2, 10 ** 6 + 2):
	if isprime[x]:
		prime.append(x)
		for i in range(2 * x, 10 ** 6 + 2, x):
			isprime[i] = False
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	sq_rt = floor(sqrt(b)) + 1
	index = bisect(prime, sq_rt)
	arr = prime[:index]
	ans = 0
	if a <= 1:
		a = 2
	isprime = [True] * (b - a + 1)
	for x in arr:
		st = floor(a / x) * x
		if st < a:
			st += x
		if st == x:
			st += x
		st = st - a
		for y in range(st, b - a + 1, x):
			if isprime[y] == True:
				isprime[y] = [x]
			else:
				isprime[y].append(x)
	for x in range(b - a + 1):
		if isprime[x] == True:
			ans += 1
		else:
			temp = 1
			val = a + x
			if sqrt(val) == int(sqrt(val)):
				c = 0
				while val > 1 and c < len(isprime[x]):
					elem = isprime[x][c]
					t = 0
					while val % elem == 0:
						t += 1
						val = val // elem
					temp *= 1 + t
					c += 1
				pos = bisect(prime, temp) - 1
				if prime[pos] == temp:
					ans += 1
			else:
				continue
	print(ans)


import bisect
import itertools

class Main:

	def __init__(self):
		iterable = self.__standard()
		self.__solution(iterable)

	def __solution(self, iterable):
		(cases,) = map(int, next(iterable).split())
		one = 10 ** 6
		two = 10 ** 3
		primes0 = [number for (number, really) in enumerate(self.__sieve(one)) if really]
		primes = set(primes0)
		for _test in range(cases):
			(low, high) = map(int, next(iterable).split())
			total = 0
			for number in range(two):
				if number not in primes:
					continue
				value = number
				exponent = 2
				while not value > high:
					if not value < low and exponent in primes:
						total += 1
					value *= number
					exponent += 1
			linear = bisect.bisect_right(primes0, high) - bisect.bisect_left(primes0, max(low, two))
			if linear > 0:
				total += linear
			for number in range(two + 1, min(high + 1, one), 2):
				if number not in primes:
					continue
				square = number * number
				if square > high:
					break
				if not square < low:
					total += 1
			sieveLow = max(one, low)
			sieveHigh = high + 1
			if sieveHigh > sieveLow:
				sieve = [True] * (sieveHigh - sieveLow)
				for prime in primes0:
					first = -sieveLow % prime
					count = (len(sieve) - first - 1) // prime + 1
					sieve[first::prime] = [False] * count
				total += sum(sieve)
			print(total)

	def __sieve(self, limit):
		size = limit + 1
		sieve = [True]
		head = []
		for prime in self.__generator():
			previous = len(sieve)
			count = previous * prime
			if not count < size:
				break
			sieve *= prime
			sieve[::prime] = [False] * previous
			head.append(prime)
		sieve *= (size - 1) // len(sieve) + 1
		del sieve[size:]
		sieve[1] = False
		for last in head:
			sieve[last] = True
		first = last + 2
		for prime in itertools.count(first, 2):
			square = prime * prime
			if square > limit:
				break
			if not sieve[prime]:
				continue
			step = prime << 1
			count = (size - square - 1) // step + 1
			sieve[square::step] = [False] * count
		return sieve

	def __generator(self):
		yield 2
		for candidate in itertools.count(3, 2):
			for divisor in itertools.count(3, 2):
				if divisor * divisor > candidate:
					yield candidate
					break
				if not candidate % divisor:
					break

	def __test(self):
		yield '1'
		yield '1 10'

	def __standard(self):
		try:
			while True:
				yield input()
		except EOFError:
			pass
Main()