Since the number of test cases is quite large, the System.out.println() command gets invoked a lot many times. To avoid that, you could use a PrintWriter for efficiency, or a StringBuilder to store output into and finally print it out just the one time (or both, which is what I do). You could check out my solution to the same, mainly the StringBuilder portion.

Do give this a read as well. It compares the performance of different printing methods. Note that with interactive problems, since you need to flush the output after each interaction, you'll have to change your approach (I use good old System.out.println() there)

Also while I like how you implement the Sieve, I think there's room for some optimization there as well. (My approach is slightly different compared to yours but if you compare against squares in mine, that'll lead to Integer Overflow, which I address by some different form of comparison)

Lastly, happy learning :)