1006 GCD Game

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>

#define fi first
#define se second

#define lowbit(x) (x&-x)

using namespace std;

namespace ae86{
    const int bufl=1<<15;
    char buf[bufl],*s=buf,*t=buf;
    inline int fetch(){
        if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
        return*s++;
    }
    inline int read(){
        int a=0,b=1,c=fetch();
        while(!isdigit(c))b^=c=='-',c=fetch();
        while(isdigit(c))a=a*10+c-48,c=fetch();
        return b?a:-a;
    }
}
using ae86::read;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,double> pid;

const int inf=0x3f3f3f3f;
const ll INF=2e18;
const double eps=1e-8;
const double pi=acos(-1);
const int mod=1e9+7;

const int N=1000010;

int T;
int n;
int a[N];
int primes[N*10],cnt[N*10];
bool st[N*10];

void get_primes(int n){
    int tot=0;
    for(int i=2;i<=n;i++){
        if(!st[i])  primes[tot++]=i,cnt[i]=1;
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            cnt[primes[j]*i]=cnt[i]+1;
            if(i%primes[j]==0)  break;
        }
    }
}

int main(){
    T=read();
    get_primes(1e7);
    while(T--){
        n=read();
        int res=0;
        for(int i=1;i<=n;i++){
            a[i]=read();
            if(a[i]==1)    continue;
            res^=cnt[a[i]];
        }
        if(n==1&&a[1]==1)    puts("Bob");
        else if(n==1)    puts("Alice");
        else if(res)    puts("Alice");
        else puts("Bob");
    }
}