DCEPC807 - Bit by Bit

Alice and Bob play an interesting game. They start with a number “n” and follow some rules until the game ends. The rules for the game are:

  1. Let F(n) denotes the total number of set bits in binary representation of numbers from 0 to 2n - 1.
  2. Each player plays alternatively until the game ends and one of them wins the game.
  3. In each turn a player either unsets a single set bit from binary representation of “n” or unsets 2 consecutive set bits from the binary representation of “n”. Let’s call the resulting number after such move as “x”.
  4. The game ends when F(x) is a power of 2. (0 is also a power of 2).
  5. The player with no move loses the game and so other player wins the game.
  6. Alice starts the game always.
  7. Both of them play optimally.

Given “n” can you predict the winner of the game?

Input

First line contains T, the number of test cases.

Next T lines contains one integer per line, “n” (quotes for clarity).

Output

Output T lines, each containing either “Alice” if Alice wins the game or “Bob” if Bob wins the game. 

Constraints

1 ≤ T ≤ 10

0 ≤ n ≤ 106

Example

Input:
2
4
10

Output:
Bob
Alice

Added by:dce coders
Date:2012-08-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem

hide comments
2012-08-28 08:18:17 Alex Anderson
You should mention that they play optimally. Otherwise the problem statement doesn't ensure that games will be played the same each time, and it is not the case that every possible playthrough of a game will result in the same winner.

> Thanks for pointing that out..corrected :)

Last edit: 2012-08-28 08:19:34
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.