for i in range(t):
Can you share the problem link?
First of all its a problem related to the field of Combinatorial Game Theory but all Combinatorial Game Theory problem are not this much easy. However, in this type of problems or in any game related problem try to find is there any pattern evolving, and if there is then how can I exploit that pattern to get the answer.
In most of the pattern solving problem you can use OEIS.