Submitting your recent hacked solution adding in

import sys 
input = sys.stdin.readline

ACs in 326ms/2000 ms.

In problems with many testcases, calling print $$$T$$$ times, can be very slow, so it can be much faster to store all $$$T$$$ answers in an array out and call

print('\n'.join(map(str, out)))

once at the end of your programs.

It happened again, this time in C++ :(

Now, you've hacked the editorialist's solution itself.