Also, printing each answer one by one is not a good idea for this problem, unfortunately. If T = 10^6, your code prints the answer 10^6 times, which may lead to TLE. I also had this issue and fixed it by collecting them in StringBuilder. See here: CodeChef: Practical coding for everyone
It somehow works in 1.65 sec. By the way, I/O speed is another concern as well.
Once the input/output size reaches 10^5, the I/O should always be a concern, and it may take non-trivial amount of time just to read the problem data and write the answers. It’s just one thing to keep in mind always.
Already fixed the link. Yeah, I understand that. I got this issue in some long contest before and it is so annoying. Using Buffered Reader and do not print too often are always the best options.