Q : A function F , which takes input x is defined as follows
F(x) = 1, if sum of digits of x is prime
F(x) = 0, otherwise

Given T test cases,
Each test case has 2 inputs L and R
you should print "ans",
where ans is number of prime numbers between L and R i.e.,.

ans = 0
for (int i = L; i <= R; ++i){
	ans = ans + F( sumOfDigits(i) ) 
return ans 

T <= 10^4
L, R <= 10^18

My approach

i noticed that maximum L,R would be 10^18.
Since we only care about sum of digits , the maximum sum of digits is achieved when
R = 999999999999999999 ( 9 repeated 18 times)
Maxsum of digits = 9*18 < 200

So i precomputed primes upto 200 using SOE
then i iterated from L to R and decided in O(1) whether it is prime or not.

pseudo code

T = # test cases
while T < 0:
	prime = SOE(200) 
	L, R = input()
	ans = 0
	
	for (int i = L; i <= R; ++i) {
		sumOfDigits = getSumOfDigits(i) 
		if (prime[ sumOfDigits ] == True) {
				 ans += 1
		}			
	}
	print(ans)
	T -= 1

I thought this was it, but it able to pass only 4 test cases out of 20.
I was getting time limit exceeded.

So i know i am missing some major idea, so please help me.

I also tried some optimizations like
Instead of everytime calculating sumOfDigits of i, just calculate it when last digit is 0, and go on adding 1 to previous sumOfDigits

eg:
sumOfDigits(30) = 3 // i calculate it
sumOfDigits(31) = 4 // + 1 , add 1 to previously calculated sumOfDigits
sumOfDigits(32) = 5 // + 1
sumOfDigits(33) = 6 // + 1
...
sumOfDigits(39) = 12
sumOfDigits(40) = 40 // last digit is 0 , also this is where sumOfDigits resets so i will calculate it

But it was no improvement , i cound still pass only 4 test cases.