N integers 1, 2, 3, \ldots N are placed on a circle in clockwise order such that i and (i+1) are adjacent for all 1 ≤ i ≤ N - 1, and 1 and N are also adjacent.

Given an integer K, Ashish repeatedly removes integers from the circle until only one integer remains. He does so in the following manner. In each move, Ashish finds the integer which is on the K-th place from the smallest one in clockwise order and removes it from the circle, i.e. its neighbours now become adjacent.

For example, consider the case when N = 3 and K = 3. Let the circular array [1, 2, 3] denote the integers on the circle. In the first move, 3 is removed since it is the K-th integer starting from 1, which is the smallest integer currently on the circle. Likewise, in the next move 1 is removed and finally only 2 remains. [1, 2, \underline{3}] \rightarrow [\underline{1}, 2] \rightarrow [2].

Since N and K may be very large, Ashish cannot simulate the process himself. Help him find the parity of the last integer that remains after the repeated removals. In other words, report if this integer is odd or even.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two integers N and K.

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

For each test case, output ODD if the last integer that remains after the repeated removals is odd, and EVEN otherwise.

Each letter of the output may be printed in either lowercase or uppercase. For example, the strings odd, Odd, and ODD will all be treated as equivalent.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{18}$
$1 ≤ K ≤ N$

----- Sample Input 1 ------ 
4
4 1
3 3
9 1
3489601027782 8104267
----- Sample Output 1 ------ 
EVEN
EVEN
ODD
EVEN
----- explanation 1 ------ 
Test case $1$: The last integer that remains is $4$, which is EVEN.

$[\underline{1}, 2, 3, 4] \rightarrow [\underline{2}, 3, 4] \rightarrow [\underline{3}, 4] \rightarrow [4]$

Test case $2$: The last integer that remains is $2$, which is EVEN.

$[1, 2, \underline{3}] \rightarrow [\underline{1}, 2] \rightarrow [2]$

Test case $3$: The last integer that remains is $9$, which is ODD.

$[\underline{1}, 2, 3, 4, 5, 6, 7, 8, 9] \rightarrow [\underline{2}, 3, 4, 5, 6, 7, 8, 9] \rightarrow \ldots \rightarrow [9]$

Difficulty: EASY
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
import itertools
import collections, math
from collections import defaultdict
from collections import Counter
import sys
import heapq
from heapq import *

def solve():
	(n, k) = [int(x) for x in input().split()]
	if k == 1:
		if n % 2:
			return 'ODD'
		else:
			return 'EVEN'
	if k == 2:
		return 'ODD'
	return 'EVEN'
for t in range(int(input())):
	print(solve())


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k == 1:
		if n % 2 == 0:
			print('EVEN')
		else:
			print('ODD')
	elif k == 2:
		print('ODD')
	else:
		print('EVEN')


def solve(a, b):
	if b == 1:
		if a % 2:
			return 'ODD'
		return 'EVEN'
	if b == 2:
		return 'ODD'
	return 'EVEN'
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(solve(a, b))


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y == 1:
		if x % 2 == 0:
			print('EVEN')
		else:
			print('ODD')
	elif y == 2:
		print('ODD')
	else:
		print('EVEN')


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	if K == 1:
		print('EVEN') if N % 2 == 0 else print('ODD')
	elif K == 2:
		print('ODD')
	else:
		print('EVEN')


a = int(input(''))
for i in range(a):
	(X, Y) = [int(x) for x in input('').split()]
	if Y == 1:
		if X % 2 != 0:
			print('ODD')
		else:
			print('EVEN')
	elif Y == 2:
		print('ODD')
	else:
		print('EVEN')


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	if K == 1:
		if N % 2 == 1:
			print('ODD')
		else:
			print('EVEN')
	elif K == 2:
		print('ODD')
	else:
		print('EVEN')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == 1:
		print('ODD')
	elif a > 1 and b == 1:
		if a % 2 == 0:
			print('EVEN')
		else:
			print('ODD')
	elif a > 1 and b > 2:
		print('EVEN')
	elif a > 1 and b == 2:
		print('ODD')


test = int(input())
for i in range(test):
	(din, sas) = list(map(int, input().split()))
	if sas == 1:
		if din % 2 == 0:
			print('EVEN')
		else:
			print('ODD')
	elif sas == 2:
		print('ODD')
	else:
		print('EVEN')


T = int(input())
for t in range(T):
	input_arr = str(input()).split(' ')
	N = int(input_arr[0])
	K = int(input_arr[1])
	if N == 1:
		print('ODD')
	elif K == 1:
		if N % 2 == 0:
			print('EVEN')
		else:
			print('ODD')
	elif K == 2:
		print('ODD')
	else:
		print('EVEN')


t = input()
for c in range(0, int(t)):
	(N, K) = [int(x) for x in input().split(' ')]
	if K == 1:
		if N % 2 == 0:
			print('EVEN')
		else:
			print('ODD')
	elif K == 2:
		print('ODD')
	else:
		print('EVEN')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if k == 1 and n % 2 == 1 or k == 2:
		print('ODD')
	else:
		print('EVEN')


t = int(input())
a = 'qwertyuiopasdfghjklmnbvcxz'
for i in range(t):
	s = input().split()
	n = int(s[0])
	x = int(s[1])
	if x == 1:
		if n % 2 == 0:
			print('EVEN')
		else:
			print('ODD')
	elif x == 2:
		print('ODD')
	else:
		print('EVEN')


def solution():
	(n, k) = map(int, input().split(' '))
	if n % 2 == 0 and k == 1:
		print('EVEN')
	if n % 2 != 0 and k == 1:
		print('ODD')
	if k == 2:
		print('ODD')
	if k >= 3:
		print('EVEN')
t = int(input())
while t > 0:
	t -= 1
	solution()


tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	if k == 2 or (k == 1 and n & 1):
		print('ODD')
	else:
		print('EVEN')


for i in range(int(input())):
	(n, x) = map(int, input().split())
	if x == 1:
		n = str(n)
		if int(n[-1]) % 2 == 0:
			print('EVEN')
		else:
			print('ODD')
	elif x == 2:
		print('ODD')
	else:
		print('EVEN')


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	if k == 1:
		if n % 2 == 0:
			print('EVEN')
		else:
			print('ODD')
	elif k == 2:
		print('ODD')
	else:
		print('EVEN')
	t -= 1


def solve(n, k):
	if n & 1 == 1 and k < 3:
		return 'ODD'
	elif k == 2:
		return 'ODD'
	else:
		return 'EVEN'
for t in range(int(input())):
	(n, k) = [int(el) for el in input().split()]
	print(solve(n, k))


t = int(input())
for i in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	if k % 2 == 1:
		if k == 1:
			if n & 1 == 0:
				print('EVEN')
			else:
				print('ODD')
		else:
			print('EVEN')
	else:
		n = k - 1
		if n == 1:
			print('ODD')
		else:
			print('EVEN')


iT = int(input())
for itr1 in range(0, iT):
	(iN, iK) = map(int, input().split())
	if iK == 1:
		iAns = iN
	elif iK == 2:
		iAns = 1
	else:
		iAns = 2
	if iAns % 2 == 0:
		print('EVEN')
	else:
		print('ODD')


for _ in range(int(input())):
	(i, j) = map(int, input().split())
	if j == 1 and i % 2 != 0 or j == 2:
		print('ODD')
	else:
		print('EVEN')


for _ in range(int(input())):
	i = list(map(int, input().split()))
	if i[1] == 1 and i[0] % 2 != 0:
		print('ODD')
	elif i[1] == 2:
		print('ODD')
	else:
		print('EVEN')


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	if y == 1 and x & 1 or y == 2:
		print('ODD')
	else:
		print('EVEN')


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	n = l[0]
	k = l[1]
	if k == 2 or (n % 2 == 1 and k == 1):
		print('ODD')
	else:
		print('EVEN')


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if b == 1:
		if a % 2 == 0:
			print('EVEN')
		else:
			print('ODD')
	elif b == 2:
		print('ODD')
	else:
		print('EVEN')