Is this priority or parity! solution codechef

Is this priority or parity! solution codechef

NN integers 1,2,3,N1,2,3,…N are placed on a circle in clockwise order such that ii and (i+1)(i+1) are adjacent for all 1iN11≤i≤N−1, and 11 and NN are also adjacent.

Given an integer KK, 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 KK-th place from the smallest one in clockwise order and removes it from the circle, i.e. its neighbours now become adjacent.

Is this priority or parity! solution codechef

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

Since NN and KK 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 TT — the number of test cases. Then the test cases follow.
  • The first and only line of each test case contains two integers NN and KK.

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 oddOdd, and ODD will all be treated as equivalent.

Constraints

  • 1T1051≤T≤105
  • 1N10181≤N≤1018
  • 1KN1≤K≤N

Sample Input 1

Is this priority or parity! solution codechef

4
4 1
3 3
9 1
3489601027782 8104267

Sample Output 1 

EVEN
EVEN
ODD
EVEN

Explanation

Is this priority or parity! solution codechef

Test case 11: The last integer that remains is 44, which is EVEN.

[1,2,3,4][2,3,4][3,4][4][1_,2,3,4]→[2_,3,4]→[3_,4]→[4]

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

[1,2,3][1,2][2][1,2,3_]→[1_,2]→[2]

Test case 33: The last integer that remains is 99, which is ODD.

[1,2,3,4,5,6,7,8,9][2,3,4,5,6,7,8,9][9]

SOLUTION

Click Here

Leave a Comment

Your email address will not be published.