Alice and Bob are playing a game. At first, there are ~N~ positive integers written on the blackboard. They then take turns making a move, with Alice going first, which consists of the following: choose any integer ~X~ on the blackboard, erase ~X~, and write ~2~ positive integers ~Y~ and ~Z~ on the blackboard, such that ~Y \cdot Z=X~ and ~\gcd(Y,Z) > 1~. The first player who is unable to make a move loses. Find who wins the game if both players play optimally.

Constraints

~1 \le N \le 5\,000~

~2 \le A_i \le 10^{12}~

Subtask 1 [10%]

~A_i~ is a power of ~2~.

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line contains the integer ~N~.

The next line contains ~N~ space-separated integers, representing the list ~A~ of positive integers initally written on the blackboard.

Output Specification

Output ALICE if Alice wins, otherwise output BOB.

Sample Input

3
36 72 108

Sample Output

ALICE