The constraints are N ≤ 10^9 and the above is an O(N^2) solution. The problem’s time limit is 5 seconds (multiplier for python), and the above solution takes 0.71 seconds.
Theoretically, this is supposed to take 9999999990 seconds (Assuming 10^8 operations ≈1 second) for the worst case for each testcase. There are 1000 testcases at max.
It would take at least 10 times more as the language is python.
If you amortize the complexity, both of our solutions have the same O(log_2 n)
Also, please note that I solved the problem during the contest. After the contest ends, one can improve their solution by spending more time on it. During the contest, you’d just want to solve a problem and move on.