Tuzik and Vanya are playing the following game.
They have an N × M board and a chip to indicate the current game position. The chip can be placed on any one cell of the game board, each of which is uniquely identified by an ordered pair of positive integers (r, c), where 1 ≤ r ≤ N is the row number and 1 ≤ c ≤ M is the column number.
Initially, the chip is placed at the cell identified as (1, 1). For his move, a player can move it either 1, 2 or 3 cells up, or 1 or 2 cells to the right. The player who can not move the chip loses. In other words, a player suffers defeat if the chip is placed in the cell (N, M) at the start of his turn.
Tuzik starts the game. You have to determine who will win the game if both players play optimally.

-----Input-----
The first line contains an integer T denoting the number of tests. Each of the following T lines contain two integers N and M.

-----Output-----
For each test output "Tuzik" or "Vanya" on a separate line, indicating who will win the game.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ N, M ≤ 106

-----Example-----
Input:
2
4 4
2 2

Output:
Tuzik
Vanya


-----Explanation-----Test case 1: On his first turn Tuzik moves chip 3 cells up to the cell (4, 1). On his turn Vanya can move chip only right to the cell (4, 2) or to the cell (4, 3) and after that Tuzik moves it to (4, 4) and finishes the game.

Test case 2: On his first Turn Tuzik can move chip to the cell (2, 1) or (1, 2), but on his next turn Vanya moves it to (2, 2) and wins the game.

Difficulty: HARD
Tags: Implementation

Starter code:

Solutions:
from functools import reduce

def movimientos(i, j):
	for movsI in range(0, i):
		yield (movsI, j)
	for movsJ in range(0, j):
		yield (i, movsJ)

def posicionGanadora(i, j):
	return reduce(lambda res, sigMov: res or not posicionGanadora(sigMov[0], sigMov[1]), movimientos(i, j), False)
testCases = int(input())
for tc in range(testCases):
	(n, m) = list(map(int, input().split(' ')))
	print('Tuzik' if posicionGanadora((n - 1) % 4, (m - 1) % 3) else 'Vanya')


cases = int(input())
for _ in range(cases):
	(rows, cols) = map(int, input().split())
	if (cols - 1) % 3 == 0 and (rows - 1) % 4 == 0:
		print('Vanya')
	elif (cols - 1) % 3 != 0 and (rows - 1) % 4 == 0:
		print('Tuzik')
	elif (cols - 1) % 3 == 0 and (rows - 1) % 4 != 0:
		print('Tuzik')
	elif (cols - 1) % 3 == 1 and (rows - 1) % 4 == 1:
		print('Vanya')
	elif (cols - 1) % 3 == 2 and (rows - 1) % 4 == 2:
		print('Vanya')
	else:
		print('Tuzik')


for _ in range(int(input())):
	change = False
	(n, m) = map(int, input().split())
	if (n - 1) % 4 == (m - 1) % 3:
		print('Vanya')
	else:
		print('Tuzik')


for t in range(int(input())):
	(n, m) = map(int, input().split())
	print('Vanya' if (n - 1) % 4 == (m - 1) % 3 else 'Tuzik')


t = int(input())
for i in range(t):
	(r, c) = map(int, input().split())
	if (c - 1) % 3 == 0 and (r - 1) % 4 == 0:
		print('Vanya')
	elif (c - 1) % 3 != 0 and (r - 1) % 4 == 0:
		print('Tuzik')
	elif (c - 1) % 3 == 0 and (r - 1) % 4 != 0:
		print('Tuzik')
	elif (c - 1) % 3 == 1 and (r - 1) % 4 == 1:
		print('Vanya')
	elif (c - 1) % 3 == 2 and (r - 1) % 4 == 2:
		print('Vanya')
	else:
		print('Tuzik')


from functools import reduce

def movimientos(i, j):
	movs = [(movsI, j) for movsI in range(0, i)]
	movs.extend([(i, movsJ) for movsJ in range(0, j)])
	return movs

def posicionGanadora(i, j, memo):
	if memo[i][j] is None:
		memo[i][j] = not reduce(lambda res, sigMov: res and posicionGanadora(sigMov[0], sigMov[1], memo), movimientos(i, j), True)
	return memo[i][j]
testCases = int(input())
memo = [[False if i == 0 and j == 0 else None for i in range(3)] for j in range(4)]
for tc in range(testCases):
	(n, m) = list(map(int, input().split(' ')))
	print('Tuzik' if posicionGanadora((n - 1) % 4, (m - 1) % 3, memo) else 'Vanya')


t = int(input())
for i in range(t):
	n = input().split(' ')
	for i in range(2):
		n[i] = int(n[i])
	l = n[1] % 3
	if n[1] % 3 == 0:
		l = 3
	if n[0] % 4 == l:
		print('Vanya')
	else:
		print('Tuzik')