Bob and Ben are playing a game with forests! The game's rules are as follows:

The game starts with a forest of $n$ trees.
Bob always moves first and they take alternating turns. The first player with no available move loses the game.
During each move, the player removes one node. If the node is not a leaf, then the whole tree vanishes; otherwise, the rest of the tree remains in the forest. We define a leaf to be a node with exactly $1$ connected edge.
Both players play optimally, meaning they will not make a move that causes them to lose the game if some better, winning move exists.

We define each tree $\boldsymbol{i}$ in the $n$-tree forest as follows:

Tree $\boldsymbol{i}$ is defined by two integers, $m_i$ (the number of nodes in the tree) and $k_i$ (a constant). 
Its nodes are numbered sequentially from $1$ to $m_i$.
Its edges are numbered sequentially from $1$ to $m_i-1$, and each edge $j$ connects node $j+1$ to node $\lfloor\max(1,\frac{j}{k_i})\rfloor$.

Given the values of $m_i$ and $k_i$ for each tree in the forest, can you determine who will win the game?

Input Format

The first line contains an integer, $\mathrm{~g~}$, denoting the number of games. The subsequent lines describe each game in the following format:

The first line contains an integer, $g$, denoting the number of trees in the forest.     
Each of the $n$ subsequent lines contains two space-separated integers describing the respective values of $m_i$ and $k_i$ for tree $\boldsymbol{i}$. 

Constraints

$1\leq g\leq100$
$1\leq n\leq10^{6}$
$1\leq m_i\leq10^9$
$2\leq k_i\leq100$
The sum of $n$ over all games is at most $10^{6}$.

Subtasks

For $50\%$ of the maximum score:

The sum of $n$ over all games is at most $10^3$.
$1\leq m_i\leq10^3$

For $25\%$ of the maximum score:

$1\leq n,m_i,g\leq10$

Output Format

For each game, print the name of the winner on a new line (i.e., BOB or BEN).

Sample Input
2
2
1 2
1 3
1
3 2

Sample Output
BEN
BOB

Explanation

Bob and Ben play the following two games:

The forest consists of $n=2$ trees containing one node each, and each tree has no edges as $m_1$ and $m_2$ are both $\mbox{I}$ (so both trees have $1-1=0$ edges). The sequence of moves is as follows: 

We then print the name of the winner, BEN, on a new line.

The forest consists of $n=1$ tree containing three nodes. We find the $m_1-1=2$ edges like so: 

Edge $j=1$ connects node $j+1=2$ to node $floor(max(1,\frac{j}{k_1}))=floor(max(1,\frac{1}{2}))=1$.
Edge $j=2$ connects node $j+1=3$ to node $floor(max(1,\frac{j}{k_2}))=floor(max(1,\frac{2}{2}))=1$.       

The game then plays out as follows: 

We then print the name of the winner, BOB, on a new line.

Source: hackerrank | Difficulty: MEDIUM
Tags: Game theory


Solutions:
import sys
for _ in range(int(sys.stdin.readline())):
	(ones, twos, rest) = (0, 0, 0)
	n = int(input())
	for i in range(n):
		(m, k) = map(int, sys.stdin.readline().split())
		if m == 1:
			ones += 1
		elif m == 2:
			twos += 1
		else:
			rest += m
	if (ones % 2, twos % 2, rest % 2, n % 2) in [(1, 0, 1, 0), (0, 0, 0, 0), (1, 1, 1, 1), (0, 1, 0, 1)]:
		print('BEN')
	else:
		print('BOB')


g = int(input())
for _ in range(g):
	n = int(input())
	score = 0
	for _ in range(n):
		(m, k) = map(int, input().split())
		if m % 2 == 1:
			score ^= 1
		elif m > 2:
			score ^= 2
	print('BEN' if score == 0 else 'BOB')


player = {1: 'BOB', 2: 'BEN'}
g = int(input())
for _ in range(g):
	n = int(input())
	(x, y) = (0, 0)
	for i in range(n):
		(m, k) = map(int, input().split())
		if m % 2 == 1:
			x += 1
		elif m != 2:
			y += 1
	if x % 2 == 0 and y % 2 == 0:
		print(player[2])
	else:
		print(player[1])


t = int(input())
for test_case in range(t):
	n = int(input())
	res = 0
	for j in range(n):
		(a, b) = [int(x) for x in input().split()]
		if a % 2 == 0 and a != 2:
			res ^= 2
		elif a % 2 != 0:
			res ^= 1
	if res == 0:
		print('BEN')
	else:
		print('BOB')


import sys
g = int(sys.stdin.readline())
for it in range(g):
	n = int(sys.stdin.readline())
	(m, k) = zip(*[map(int, sys.stdin.readline().split()) for i in range(n)])
	xor = 0
	for i in m:
		if i == 1:
			i = 1
		elif i == 2:
			i = 0
		else:
			i = 2 if i % 2 == 0 else 1
		xor = xor ^ i
	print('BOB' if xor else 'BEN')


def win(m, n):
	if n % 2:
		return True
	else:
		return sum(m) % 2
for _ in range(int(input())):
	n = int(input())
	m = []
	for i in range(n):
		mi = next(map(int, input().split()))
		if mi != 2:
			m.append(mi)
	print(('BEN', 'BOB')[win(m, len(m))])


g = int(input())
while g != 0:
	n = int(input())
	sum = 0
	even = 0
	while n != 0:
		m = int(input().split()[0])
		if m % 2 == 0 and m != 2:
			even += 1
		sum = sum + m
		n -= 1
	if sum % 2 == 0:
		if even % 2 == 0:
			print('BEN')
		else:
			print('BOB')
	elif even % 2 == 0 or even == 1:
		print('BOB')
	else:
		print('BOB')
	g = g - 1


def solve():
	n = int(input())
	a = 0
	for i in range(n):
		(m, k) = map(int, input().split())
		if m == 2:
			m = 0
		else:
			m = 1 + (m - 1) % 2
		a = a ^ m
	if a == 0:
		print('BEN')
	else:
		print('BOB')
g = int(input())
for i in range(g):
	solve()


g = int(input().strip())
for i in range(g):
	n = int(input().strip())
	trees = []
	mini_nodes = 999999
	dis_trees = 0
	indis_trees = 0
	additional_nodes = 0
	for i in range(n):
		(m, k) = map(int, input().split())
		trees.append((m, k))
		if m == 1:
			indis_trees += 1
		elif m == 2:
			indis_trees += 2
		else:
			dis_trees += 1
			if m < mini_nodes:
				mini_nodes = m
			if m > 3:
				additional_nodes += m - 3
	no_trees = dis_trees + indis_trees
	if no_trees % 2 == 0:
		if additional_nodes % 2 == 1:
			print('BOB')
		if additional_nodes % 2 == 0:
			print('BEN')
	else:
		print('BOB')


for _ in range(int(input().strip())):
	xorsum = 0
	for _ in range(int(input().strip())):
		(m, k) = [int(x) for x in input().strip().split(' ')]
		xorsum ^= 0 if m == 2 else 2 - m % 2
	print('BOB' if xorsum else 'BEN')


for g in range(int(input())):
	n = int(input())
	nim_sum = 0
	for i in range(n):
		(m, k) = map(int, input().split())
		if m == 1:
			nim_sum ^= 1
		elif m > 2:
			if m % 2 == 1:
				nim_sum ^= 1
			else:
				nim_sum ^= 2
	print(['BEN', 'BOB'][nim_sum > 0])


from functools import reduce
t = int(input())
for _ in range(t):
	n = int(input())
	trees = []
	for i in range(n):
		(node, m) = (int(i) for i in input().split())
		if node == 2:
			trees.append(0)
		else:
			trees.append(1 if node % 2 == 1 else 2)
	temp = reduce(lambda x, y: x ^ y, trees)
	if temp == 0:
		print('BEN')
	else:
		print('BOB')


def grundy(g):
	if g == 0 or g == 2:
		return 0
	elif g & 1:
		return 1
	else:
		return 2
for g in range(int(input())):
	n = int(input())
	trees = dict()
	ans = 0
	for tree in range(n):
		(m, k) = [int(x) for x in input().strip().split()]
		ans ^= grundy(m)
	print('BOB' if ans != 0 else 'BEN')


t = int(input())
for test_case in range(t):
	n = int(input())
	res = 0
	for j in range(n):
		(a, b) = [int(x) for x in input().split()]
		if a % 2 == 0 and a != 2:
			res ^= 2
		elif a % 2 != 0:
			res ^= 1
	if res == 0:
		print('BEN')
	else:
		print('BOB')


T = int(input())
for i in range(T):
	sg = 0
	n = int(input())
	for j in range(n):
		(m, k) = map(int, input().split())
		if m != 2:
			sg ^= 2 - m % 2
	if sg:
		print('BOB')
	else:
		print('BEN')


from functools import reduce
from operator import xor

def grundy(m):
	if m == 2:
		return 0
	else:
		return 1 if m % 2 else 2
for _ in range(int(input())):
	trees = [[int(x) for x in input().split()] for _ in range(int(input()))]
	print('BOB' if reduce(xor, (grundy(m) for (m, _) in trees), 0) else 'BEN')


t = int(input())
for _ in range(t):
	n = int(input())
	G = 0
	for __ in range(n):
		(m, k) = [int(i) for i in input().split()]
		if m > 2:
			G ^= (m - 1 & 1) + 1
		else:
			G ^= m & 1
	if G:
		print('BOB')
	else:
		print('BEN')


for i in range(int(input())):
	g = 0
	for j in range(int(input())):
		(m, k) = map(int, input().split())
		if m == 0 or m == 2:
			g = g
		elif m == 1:
			g ^= 1
		else:
			g ^= (m + 1) % 2 + 1
	print('BOB' if g else 'BEN')


a = int(input().strip())
ll = []
for tt in range(a):
	w = int(input().strip())
	lll = []
	c = 0
	for s in range(w):
		g = tuple(map(int, input().strip().split(' ')))
		lll.append(g)
	ll.append(lll)
for i in ll:
	c = 0
	c1 = 0
	for s in i:
		if s[0] != 2 and s[0] % 2 == 0:
			c += 1
		if s[0] % 2 == 1:
			c1 += 1
	if c1 % 2 == 0 and c % 2 == 1:
		print('BOB')
	if c1 % 2 == 0 and c % 2 == 0:
		print('BEN')
	if c1 % 2 == 1 and c % 2 == 0:
		print('BOB')
	if c1 % 2 == 1 and c % 2 == 1:
		print('BOB')


from collections import defaultdict
g = int(input())
for _ in range(g):
	n = int(input())
	graphs = []
	odds = []
	evens = []
	total_nodes = 0
	for _ in range(n):
		(nodes, k) = [int(x) for x in input().strip().split()]
		total_nodes += nodes
		if nodes % 2 == 1:
			odds.append(nodes)
		elif nodes == 2:
			odds.append(1)
			odds.append(1)
		else:
			evens.append(nodes)
	if total_nodes % 2 == 1:
		print('BOB')
	elif (len(odds) + len(evens)) % 2 == 1:
		print('BOB')
	else:
		print('BEN')


for _ in range(int(input())):
	s = 0
	for _ in range(int(input())):
		(n, e) = map(int, input().split(' '))
		s ^= n & 1 if n < 3 else (n + 1 & 1) + 1
	print('BOB' if s != 0 else 'BEN')


import sys
from time import time

def layer_gen(m, k):
	yield (1, 1, 1)
	m -= 1
	if m:
		u = min(m, 2 * k - 1)
		yield (u, 1, 1)
		m -= u
	factor = 2 * k - 1
	base = k
	while m:
		u = min(m, k * factor)
		yield (u, factor, base)
		m -= u
		factor *= k
		base *= k

def nimber(m, k):
	print('\tm=%d k=%d' % (m, k), file=sys.stderr)
	if m == 0:
		return 1
	if m == 2:
		return 0
	if m % 2 == 0:
		return 2
	return 1

def solve(gg):
	print('gg=%s' % gg, file=sys.stderr)
	rval = 0
	for (m, k) in gg:
		n = nimber(m, k)
		print('\tn=%d' % n, file=sys.stderr)
		rval ^= n
	return rval > 0
tm = time()
t = int(input())
for _ in range(t):
	gg = []
	n = int(input())
	for _ in range(n):
		(m, k) = map(int, input().split())
		gg.append((m, k))
	if solve(gg):
		print('BOB')
	else:
		print('BEN')
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


import os
import sys
from functools import reduce

def G(n):
	if n == 0 or n == 2:
		return 0
	else:
		return (n - 1) % 2 + 1
for _ in range(int(input())):
	n = int(input())
	arr = []
	for _ in range(n):
		arr.append(list(map(int, input().rstrip().split()))[0])
	new_arr = map(G, arr)
	print('BOB') if reduce(lambda x, y: x ^ y, new_arr) else print('BEN')


import sys

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		G = 0
		for _ in range(N):
			(M, _) = map(int, sys.stdin.readline().split())
			if M != 2:
				G ^= 2 - (M & 1)
		sys.stdout.write('BEN\n' if G == 0 else 'BOB\n')
main()


def grundy(m, k):
	return 0 if m == 0 or m == 2 else (m - 1) % 2 + 1
for _ in range(int(input())):
	x = 0
	for _ in range(int(input())):
		(m, k) = map(int, input().split())
		x ^= grundy(m, k)
	print('BOB' if x else 'BEN')


g = int(input())
for _ in range(g):
	n_trees = int(input())
	nodes_per_tree = []
	for _ in range(n_trees):
		(nodes, constant) = map(int, input().split())
		nodes_per_tree.append(nodes)
	grundy_numbers = []
	for i in range(n_trees):
		if nodes_per_tree[i] == 0 or nodes_per_tree[i] == 2:
			grundy_number = 0
		else:
			grundy_number = (nodes_per_tree[i] - 1) % 2 + 1
		grundy_numbers.append(grundy_number)
	result = grundy_numbers[0]
	for i in range(1, n_trees):
		result ^= grundy_numbers[i]
	print('BOB' if result != 0 else 'BEN')


g = int(input())
for _ in range(g):
	n = int(input())
	score = 0
	for _ in range(n):
		(m, k) = map(int, input().split())
		if m % 2 == 1:
			score ^= 1
		elif m > 2:
			score ^= 2
	print('BEN' if score == 0 else 'BOB')


import os
import sys
for _ in range(int(sys.stdin.readline())):
	(ones, twos, rest) = (0, 0, 0)
	n = int(input())
	for i in range(n):
		(m, k) = map(int, sys.stdin.readline().split())
		if m == 1:
			ones += 1
		elif m == 2:
			twos += 1
		else:
			rest += m
	if (ones % 2, twos % 2, rest % 2, n % 2) in [(1, 0, 1, 0), (0, 0, 0, 0), (1, 1, 1, 1), (0, 1, 0, 1)]:
		print('BEN')
	else:
		print('BOB')


T = int(input())

def grundy(K):
	if K == 0 or K == 2:
		return 0
	if K % 2 == 1:
		return 1
	return 2
for _ in range(T):
	N = int(input())
	nI = 0
	nP = 0
	ans = 0
	for _ in range(N):
		(K, V) = map(int, input().split(' '))
		ans ^= grundy(K)
	if ans == 0:
		print('BEN')
	else:
		print('BOB')