Alice and Bob are playing a game. At the start of the game, there are N piles of stones, the i-th of which has A_{i} stones.

Alice and Bob alternate moves. On their move, a player does the following:
Choose one pile of stones, and discard the remaining N-1 piles.
Partition the stones in the chosen pile into exactly N new piles of stones, each containing at least 1 stone. Note that this means that the number of piles is always N.

The player who cannot make a move loses. Determine the winner of the game if Alice moves first.

------ Input Format ------ 

- The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case contains two lines of input.
- The first line of each test case contains N, the number of piles.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

------ Output Format ------ 

For every test case print exactly one line containing the answer — either "Alice" or "Bob" (without the quotes).
You can output Alice and Bob in any case (for example, the strings BOb, BOB, bob and boB will be recognized as a positive response)

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{18}$
- The sum of $N$ over all test cases doesn't exceed $ 3\cdot 10^{5}$

----- Sample Input 1 ------ 
1
3
5 7 8
----- Sample Output 1 ------ 
Alice
----- explanation 1 ------ 
In the first move, Alice can select the first pile and divide it into $3$ piles of sizes $2, 2$, and $1$. After this, Bob cannot make a move since each pile has less than $3$ stones.

Difficulty: VERY_HARD
Tags: Mathematics

Starter code:

Solutions:
from collections import Counter, defaultdict, deque
import itertools
import re
import math
from functools import reduce
import operator
import bisect
import heapq
import functools
mod = 10 ** 9 + 7
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	flg = 0
	for aa in a:
		if not 1 <= aa % (n * (n - 1)) < n:
			flg = 1
			break
	if flg:
		print('Alice')
	else:
		print('Bob')


t = int(input())
for i in range(t):
	n = int(input())
	lst = [int(x) for x in input().split()]
	m = n * (n - 1)
	result = 'Bob'
	for i in lst:
		p = i % m
		if p == 0 or p >= n:
			result = 'Alice'
	print(result)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = n * (n - 1)
	ans = 'Bob'
	for j in l:
		p = j % m
		if p == 0 or p >= n:
			ans = 'Alice'
	print(ans)


addy = int(input())
for i in range(addy):
	n = int(input())
	c = 0
	l = list(map(int, input().split()))
	for x in l:
		if x % (n * (n - 1)) == 0:
			c = 1
			break
		else:
			temp = x % (n * (n - 1))
			if temp >= n:
				c = 1
				break
	if c:
		print('Alice')
	else:
		print('Bob')


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	ans = 'Bob'
	for i in A:
		if i % (n * (n - 1)) == 0 or i % (n * (n - 1)) >= n:
			ans = 'Alice'
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	m = n * (n - 1)
	if any((el % m == 0 or el % m >= n for el in arr)):
		print('Alice')
	else:
		print('Bob')


t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	found = True
	for i in li:
		x = i % (n * (n - 1))
		if x == 0 or x >= n:
			found = True
			break
		else:
			found = False
	if found:
		print('Alice')
	else:
		print('Bob')


def check(i, n):
	l = (n - 1) * n
	l = i % l
	if l > n - 1 or not l:
		return 1
	else:
		return 0
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	bob = True
	for i in arr:
		if check(i, n):
			bob = False
			print('Alice')
			break
	if bob:
		print('Bob')


for t in range(int(input())):
	n = int(input())
	a = input().split()
	flag = 1
	for element in a:
		x = int(element) % (n * (n - 1))
		if x == 0 or x >= n:
			print('Alice')
			flag = 0
			break
	if flag:
		print('Bob')


import math
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	f = 0
	for i in range(n):
		k = ar[i] % (n * (n - 1))
		if k == 0 or k >= n:
			print('Alice')
			f = 1
			break
	if f == 0:
		print('Bob')


for i in range(int(input())):
	n = int(input())
	p = map(int, input().split())
	flag = 0
	for i in p:
		if i % (n * (n - 1)) == 0 or i % (n * (n - 1)) >= n:
			flag = 1
			break
	if flag == 1:
		print('Alice')
	else:
		print('Bob')


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	check = False
	Mod = N * (N - 1)
	for i in range(N):
		if A[i] % Mod == 0 or A[i] % Mod >= N:
			check = True
			break
	if check:
		print('Alice')
	else:
		print('Bob')


for u in range(int(input())):
	n = int(input())
	x = [int(w) for w in input().split()]
	z = n * (n - 1)
	f = True
	for i in range(n):
		if n <= x[i] % z < z or x[i] % z == 0:
			print('Alice')
			f = False
			break
	if f:
		print('Bob')


for u in range(int(input())):
	n = int(input())
	x = [int(w) for w in input().split()]
	z = n * (n - 1)
	f = True
	for i in range(n):
		if x[i] % z > 0 and x[i] % z < n:
			continue
		else:
			print('Alice')
			f = False
			break
	if f:
		print('Bob')


def solve(n, arr):
	for i in range(n):
		if arr[i] % (n * (n - 1)) not in range(1, n):
			return 'Alice'
	return 'Bob'
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve(n, arr))


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 'Bob'
	for i in a:
		if not 1 <= i % (n * (n - 1)) < n:
			ans = 'Alice'
			break
	print(ans)