Around 2 seconds for T = 100000 and max L = 25 * 10^12. The key to solve is to generate cuban primes efficiently and then use binary search for each query. In order to generate cuban primes efficiently I used a sieve for n. Sieve is indexed by n and maximum length is determined by maximum L. For every prime up to L^0.5 starting from 5 I solved quadratic congruence 3 * n^2(n + 1) + 1 = 0 (mod prime) using Tonelli-Shanks algorithm and calculating inverse modulo using extended Euclidean algorithm.

I was stranded on 50.00 points for a while before I decided to explore a method similar to the sieve of Eratosthenes.

At this point, you should have derived a formula to generate the sequence of centered hexagonal numbers (A003215) and noted that the desired cuban primes (A002407) are one of its subsequences. It suffices to maintain a sieve for all the elements in the former sequence and mark those elements that are composite. To do so, you will need to solve the formula you derived modulo p and apply the Tonelli-Shanks or Bernstein algorithm to compute square roots. You will also require an implementation of the extended Euclidean algorithm to compute modular inverses.

I had to dig deep to get this, and I have to admit I think it is a very good one, going way beyond the original Project Euler problem. This link doesnt have any answers but might help to get thinking in roughly the right direction to solve for large L:

https://mae.ufl.edu/~uhk/ERATOSTHENES.pdf

can anyone help me to decrease the time complexity of this problem?

is there is limit for value of n