from math import sqrt as sq
import sys
is_knumber = {}
knumber_count = []
def is_prime(x):
if (x < 2 ) : return False
for i in range(2,int(sq(x))+1):
if x % i == 0:
return False
return True
def calculateSumOfDivisors():
is_knumber[2] = True
for i in range(2,1001):
if is_prime(i):
pwr = i*i
sod = 1+i+i*i
while(pwr < 1000001):
if(is_prime(sod)):
is_knumber[pwr] = True
pwr *= i
sod += pwr
knumber_count.append(0)
for i in range(1,1000001):
knumber_count.append(knumber_count[i-1] + int(is_knumber.get(i,False)))
return knumber_count
if __name__=='__main__':
result = []
calculateSumOfDivisors()
t = int(input())
while (t):
t1,t2 = input().split()
result.append(knumber_count[int(t2)]-knumber_count[int(t1)-1])
t -= 1
for i in result:
print(i)
I dono how to optimize the above solution in python, can someone please help me !!! `