# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Authors:* naisheel, jalp1428

*tabr*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

1421

# PREREQUISITES:

Observation

# PROBLEM:

Alice and Bob play a game with an integer N, taking turns with Alice going first.

On their turn, a player must choose an odd prime factor of N, and subtract it from N.

Whoever cannot move loses.

Find the winner if both play optimally.

# EXPLANATION:

Let’s get an edge case out of the way first: if N = 1, Alice cannot make a move at all and loses.

Now, let’s look at N\gt 1.

Let p be an odd prime factor of N.

Then, note that p is also an odd prime factor of N-p, since N is itself a multiple of p.

This allows Bob to win whenever N is even, by just copying Alice!

- If Alice doesn’t have any moves, she loses.
- Otherwise, Alice makes some move and N becomes N-p.

Now, since N is even and p is odd, we surely have N-p\gt 0 (since N-p will be odd). - From our earlier observation, p divides N-p so Bob can always make this move, leading to N-2p (which is even).
- This way, Bob can never lose: he can just copy Alice’s move at each step.

This also tells us that Alice can always win when N is odd (and greater than 1), since:

- If N is a prime, Bob will receive N-N=0 and lose.
- Otherwise, N being odd means N always has an odd prime factor p; and Bob will receive N-p which is even.

Now the roles are reversed: after the first move, Alice can copy Bob’s moves and never lose.

This gives us a straightforward solution: Alice wins if N is odd and \gt 1, Bob wins otherwise.

# TIME COMPLEXITY

\mathcal{O}(1) per testcase.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
print('Alice' if n%2 == 1 and n > 1 else 'Bob')
```