I think it may be a struggle to solve this with Python. There are already many solvers, including from after the compiler and time-limit change, so it’s not impossible.
I don’t know much about Python, so I might be talking rubbish, but here goes…
The code adds an awful lot of numbers to lists - that’s got to take some time right? Can you pre-allocate the space for the full list rather then increase it incrementally? You re-sieve the Prime array for each test case, but the primes aren’t going to change - create the list once with the maximum size needed for these test cases and then re-use it.
The comments suggest this may be one of the cases where trial division is better than trying to sieve btw, but ymmv.
(Once you get past the TLE, I expect you’ll get WA, but that’s a question for another day.)