Codeforces Round 726 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

games

math

number theory

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Deleting Divisors

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAlice and Bob are playing a game.

They start with a positive integer $$$n$$$ and take alternating turns doing operations on it. Each turn a player can subtract from $$$n$$$ one of its divisors that isn't $$$1$$$ or $$$n$$$. The player who cannot make a move on his/her turn loses. Alice always moves first.

Note that they subtract a divisor of the current number in each turn.

You are asked to find out who will win the game if both players play optimally.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$) — the initial number.

Output

For each test case output "Alice" if Alice will win the game or "Bob" if Bob will win, if both players play optimally.

Example

Input

4 1 4 12 69

Output

Bob Alice Alice Bob

Note

In the first test case, the game ends immediately because Alice cannot make a move.

In the second test case, Alice can subtract $$$2$$$ making $$$n = 2$$$, then Bob cannot make a move so Alice wins.

In the third test case, Alice can subtract $$$3$$$ so that $$$n = 9$$$. Bob's only move is to subtract $$$3$$$ and make $$$n = 6$$$. Now, Alice can subtract $$$3$$$ again and $$$n = 3$$$. Then Bob cannot make a move, so Alice wins.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/02/2023 05:44:08 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|