Jon and Arya are playing a game. Rules of game as follows:
  They have a single number N initially.
   Both will play an alternate move. Jon starts first.
   Both will play each move optimally.
   In each move, they can perform only one of these operation
          1. Divide that number by 2, 3, 4 or 5 and take floor of result.
          2. Subtract that number by 2, 3, 4 or 5.
   If after making a move the number becomes 1, the player who made the move automatically loses the game.
   When number becomes zero, the game will stop and the player who can't make a move loses the game.
 
Example 1:
Input:
N = 3
Output:
Jon
Explanation:
Jon will just subtract 3 from initial
number and win the game.
Example 2:
Input:
N = 6
Output:
Arya
Explanation:
Jon will divide by 3 and then in next step
Arya will subtract by 2 and win the game.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function divAndSub() which takes an Integer N as input and returns a string denoting who won the game.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Game theory

Starter code: #User function Template for python3



class Solution:

    def divAndSub(self, N):

        # code here 

Solutions:
class Solution:

	def divAndSub(self, n):
		if n == 1:
			return 'Arya'
		if n < 6:
			return 'Jon'
		arr = [1, 0, 1, 1, 1, 1, 0, 0]
		for i in range(8, n + 1):
			if arr[i // 2] == 0 or arr[i // 3] == 0 or arr[i // 4] == 0 or (arr[i // 5] == 0):
				arr.append(1)
			elif arr[i - 2] == 0 or arr[i - 3] == 0 or arr[i - 4] == 0 or (arr[i - 5] == 0):
				arr.append(1)
			else:
				arr.append(0)
		return 'Jon' if arr[n] == 1 else 'Arya'


class Solution:

	def divAndSub(self, N):
		if N == 1:
			return 'Arya'
		arr = ['Arya', 'Jon']
		for i in range(2, N + 1):
			for prev in (i // 2, i // 3, i // 4, i // 5, i - 2, i - 3, i - 4, i - 5):
				if prev >= 0 and arr[prev] == 'Arya':
					arr.append('Jon')
					break
			else:
				arr.append('Arya')
		return arr[N]


class Solution:

	def divAndSub(self, N):
		if N == 1:
			return 'Arya'
		if N < 5:
			return 'Jon'
		result = [0] * (N + 1)
		for i in range(6):
			result[i] = 1
		keys = [2, 3, 4, 5]
		for i in range(6, N + 1):
			for key in keys:
				if result[i // key] == 0 or result[i - key] == 0:
					result[i] = 1
		if result[N] == 1:
			return 'Jon'
		else:
			return 'Arya'


class Solution:

	def divAndSub(self, N):
		winner_dict = {1: 'Jon', 2: 'Arya'}
		winArr = [0] * max(N + 1, 6)
		winArr[0] = 1
		winArr[1] = 2
		winArr[2] = 1
		winArr[3] = 1
		winArr[4] = 1
		winArr[5] = 1
		i = 6
		while i <= N:
			sub = [i - 2, i - 3, i - 4, i - 5]
			div = [i // 2, i // 3, i // 4, i // 5]
			flag = 0
			for s in sub:
				if s != 1 and s >= 0 and (s <= i):
					if winArr[s] == 2:
						winArr[i] = 1
						flag = 1
			for s in div:
				if s != 1 and s >= 0 and (s <= i):
					if winArr[s] == 2:
						winArr[i] = 1
						flag = 1
			if flag == 0:
				winArr[i] = 2
			i += 1
		return winner_dict[winArr[N]]


class Solution:

	def divAndSub(self, N):
		if N == 1:
			return 'Arya'
		elif N == 0:
			return 'Jon'
		li = [1, 0, 1, 1, 1, 1, 0, 0]
		move = [2, 3, 4, 5]
		for i in range(8, N + 1):
			count = 0
			for j in move:
				if i - j >= 0:
					if li[i - j] == 1:
						count += 1
					if li[i // j] == 1:
						count += 1
			if count == 8:
				li.append(0)
			else:
				li.append(1)
		return 'Jon' if li[N] == 1 else 'Arya'


class Solution:

	def divAndSub(self, N):
		if N == 1:
			return 'Arya'
		elif N <= 5:
			return 'Jon'
		can_win = [True for i in range(N + 1)]
		can_win[0] = False
		can_win[1] = True
		can_win[2] = True
		can_win[3] = True
		can_win[4] = True
		can_win[5] = True
		for i in range(2, N + 1):
			can_win[i] = not can_win[i - 2] or not can_win[i - 3] or (not can_win[i - 4]) or (not can_win[i - 5]) or (not can_win[i // 2]) or (not can_win[i // 3]) or (not can_win[i // 4]) or (not can_win[i // 5])
		return 'Jon' if can_win[N] else 'Arya'


class Solution:

	def divAndSub(self, N):
		arr = [0] * (N + 1)
		if N == 1:
			return 'Arya'
		if N < 5:
			return 'Jon'
		i = 1
		while i < 6 and i <= N:
			arr[i] = 1
			i += 1
		i = 6
		while i <= N:
			if arr[i // 2] == 0 or arr[i // 4] == 0 or arr[i // 3] == 0 or (arr[i // 5] == 0):
				arr[i] = 1
			elif arr[i - 2] == 0 or arr[i - 3] == 0 or arr[i - 4] == 0 or (arr[i - 5] == 0):
				arr[i] = 1
			else:
				arr[i] = 0
			i += 1
		if arr[N] == 1:
			return 'Jon'
		else:
			return 'Arya'


class Solution:

	def divAndSub(self, N):
		arr = [0] * (N + 1)
		arr[0] = 'L'
		arr[1] = 'W'
		if N == 1:
			return 'Arya'
		if N < 6:
			return 'Jon'
		i = 1
		while i < 6:
			arr[i] = 'W'
			i += 1
		for i in range(6, N + 1):
			if arr[i // 2] == 'L' or arr[i // 3] == 'L' or arr[i // 4] == 'L' or (arr[i // 5] == 'L'):
				arr[i] = 'W'
			elif arr[i - 2] == 'L' or arr[i - 3] == 'L' or arr[i - 4] == 'L' or (arr[i - 5] == 'L'):
				arr[i] = 'W'
			else:
				arr[i] = 'L'
		if arr[N] == 'W':
			return 'Jon'
		else:
			return 'Arya'


class Solution:

	def divAndSub(self, N):
		if N == 1:
			return 'Arya'
		if N <= 5:
			return 'Jon'
		arr = [0] * (N + 1)
		for i in range(1, 6):
			arr[i] = 1
		for j in range(6, N + 1):
			for k in range(2, 6):
				if arr[j // k] == 0 or arr[j - k] == 0:
					arr[j] = 1
					break
		if arr[N] == 1:
			return 'Jon'
		return 'Arya'


class Solution:

	def divAndSub(self, N):
		if N == 1:
			return 'Arya'
		arr = [1] * (N + 1)
		arr[1] = 1
		for i in range(2, 6):
			arr[i] = 0
		for i in range(6, N + 1):
			for j in [i - 2, i - 3, i - 4, i - 5, int(i / 2), int(i / 3), int(i / 4), int(i / 5)]:
				if j is not 1 and arr[j] == 1:
					arr[i] = 0
					break
		if arr[N] == 0:
			return 'Jon'
		else:
			return 'Arya'


class Solution:

	def divAndSub(self, N):
		a = [0] * (N + 1)
		if N == 1:
			return 'Arya'
		if N < 5:
			return 'Jon'
		for i in range(1, 6):
			a[i] = 1
		for i in range(6, N + 1):
			if a[i // 2] == 0:
				a[i] = 1
			elif a[i - 2] == 0:
				a[i] = 1
			if a[i // 3] == 0:
				a[i] = 1
			elif a[i - 3] == 0:
				a[i] = 1
			if a[i // 4] == 0:
				a[i] = 1
			elif a[i - 4] == 0:
				a[i] = 1
			if a[i // 5] == 0:
				a[i] = 1
			elif a[i - 5] == 0:
				a[i] = 1
		if a[N] == 1:
			return 'Jon'
		else:
			return 'Arya'


import sys

class Solution:

	def divAndSub(self, n):
		sys.setrecursionlimit(10 ** 6 + 3)
		a = [-1] * (n + 1)
		a[0] = 0

		def win(n):
			if n == 1:
				a[n] = 1
				return 1
			if a[n] != -1:
				return a[n]
			if n == 2 or n == 3 or n == 4 or (n == 5):
				a[n] = 1
				return 1
			if win(n - 2) == 0 or win(n - 3) == 0 or win(n - 4) == 0 or (win(n - 5) == 0) or (win(n // 2) == 0) or (win(n // 3) == 0) or (win(n // 4) == 0) or (win(n // 5) == 0):
				a[n] = 1
				return 1
			a[n] = 0
			return 0
		if n == 1:
			return 'Arya'
		k = win(n)
		if k == 1:
			return 'Jon'
		else:
			return 'Arya'
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.divAndSub(N))


class Solution:

	def divAndSub(self, n):
		if n == 1:
			return 'Arya'
		dp = []
		for i in range(n + 1):
			dp.append(0)
		dp[0] = 0
		for i in range(1, n + 1):
			dp[i] = 0
			for j in range(2, 6):
				if i - j >= 0 and dp[i - j] == 0:
					dp[i] = 1
				if dp[i // j] == 0:
					dp[i] = 1
		if dp[n] == 1:
			return 'Jon'
		else:
			return 'Arya'


class Solution:

	def divAndSub(self, N):
		if N == 1:
			return 'Arya'
		import math
		dp = {}

		def CanWin(N):
			if N == 1:
				return True
			if N == 0:
				return False
			if N in dp:
				return dp[N]
			for i in range(2, 6):
				for j in ['/', '-']:
					if j == '/':
						y1 = CanWin(math.floor(N / i))
						if not y1:
							return True
					else:
						y1 = CanWin(N - i)
						if not y1:
							dp[N] = True
							return True
			dp[N] = False
			return False
		x = CanWin(N)
		if x == True:
			return 'Jon'
		else:
			return 'Arya'


class Solution:

	def divAndSub(self, N):
		if N == 1:
			return 'Arya'
		dp = [0] * (N + 1)
		for i in range(1, N + 1):
			dp[i] = 0
			for j in range(2, 6, 1):
				if dp[int(i / j)] == 0:
					dp[i] = 1
				if i - j >= 0 and dp[i - j] == 0:
					dp[i] = 1
		if dp[N] == 1:
			return 'Jon'
		else:
			return 'Arya'