Problem: A pile has n stones and 2 players: Player A go first. Each move, the player will take k stones from the pile, where k has to be prime. Whoever can't make a move first is lost. Problem has multiple test. Constraints: $$$1 <= t <= 100$$$: Number of tests $$$2 <= n <= 3 \cdot 10^6$$$: The number of stones in the pile Output: A if A wins, B if B wins.
its not a nim problem though (get it?)
Try applying sprague grundy theorem, You'll notice a pattern in it and after noticing it, you can come up to an O(1) solution.
You can study it from here How to calculate Grundy values?.
Pattern looks somewhat like this g(x) = x % 4
Basically player B wins only when n % 4 == 0 otherwise A wins.
So not always B wins when n % 4 == 0
bs logic
Some more possible variations of Nim to brighten your day