Chef and Paja are bored, so they are playing an infinite game of ping pong. The rules of the game are as follows:
- The players play an infinite number of games. At the end of each game, the player who won it scores a point.
- In each game, one of the players serves. Chef serves in the first game.
- After every $K$ points are scored (regardless of which players scored them), i.e. whenever $K$ games have been played since the last time the serving player changed, the player that serves in the subsequent games changes: if Chef served in the game that just finished, then Paja will serve in the next game and all subsequent games until the serving player changes again; if Paja served, then Chef will serve.
The players got a little too caught up in the game and they forgot who is supposed to serve in the next game. Will you help them determine that? So far, Chef has scored $X$ points and Paja has scored $Y$ points.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains three space-separated integers $X$, $Y$ and $K$.

-----Output-----
For each test case, print a single line containing the string "Chef" if Chef is supposed to serve next or "Paja" otherwise (without quotes).

-----Constraints-----
- $1 \le T \le 50$
- $0 \le X, Y \le 10^9$
- $1 \le K \le 10^9$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
3
1 3 3
5 7 2
38657 76322 564

-----Example Output-----
Paja
Chef
Paja

-----Explanation-----
Example case 1: Chef served for the first three games, after that Paja started serving. He only served in one game, so he is supposed to serve next.

Difficulty: EASY
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(x, y, k) = map(int, input().split())
	ans = (x + y) // k
	if ans % 2 == 0:
		print('Chef')
	else:
		print('Paja')


t = int(input())
for i in range(t):
	(x, y, k) = list(map(int, input().split()))
	if x + y < k:
		print('Chef')
	elif (x + y) // k % 2 == 0:
		print('Chef')
	elif (x + y) // k % 2 != 0:
		print('Paja')


for i in range(int(input())):
	(a, b, c) = map(int, input().split())
	print('Chef' if (a + b) % (2 * c) < c else 'Paja')


t = int(input())
while t > 0:
	(x, y, k) = map(int, input().split(' '))
	z = x + y
	a = z // k
	if a % 2 == 0:
		print('Chef')
	else:
		print('Paja')
	t = t - 1


for t in range(int(input())):
	(x, y, z) = tuple(map(int, input().split()))
	if (x + y) // z % 2 == 0:
		print('Chef')
	else:
		print('Paja')


import math
for i in range(int(input())):
	(x, y, k) = map(int, input().split())
	if math.trunc((x + y) / k % 2) == 0:
		print('Chef')
	else:
		print('Paja')


l = int(input())
for i in range(l):
	(X, Y, k) = input().split()
	X = int(X)
	Y = int(Y)
	k = int(k)
	if (X + Y) % (2 * k) < k:
		print('Chef')
	else:
		print('Paja')


for o in range(int(input())):
	(x, y, k) = list(map(int, input().split()))
	tot = x + y
	if tot // k % 2 == 0:
		print('Chef')
	elif tot // k % 2 == 1:
		print('Paja')


t = int(input())
while t > 0:
	(a, b, c) = map(int, input().split())
	n = (a + b) // c
	if n % 2 == 0:
		print('Chef')
	else:
		print('Paja')
	t -= 1


for _ in range(int(input())):
	(A, B, C) = map(int, input().split())
	n = (A + B) // C
	if n % 2 == 0:
		print('Chef')
	else:
		print('Paja')


t = int(input())
for i in range(t):
	(x, y, k) = map(int, input().split())
	z = (x + y) % (2 * k)
	if z < k:
		print('Chef')
	else:
		print('Paja')


import math
t = int(input())
for i in range(t):
	(x, y, k) = map(int, input().split())
	z1 = math.ceil((x + y) / k)
	z2 = math.floor((x + y) / k)
	if z1 == z2 and z1 % 2 == 0:
		print('Chef')
	elif z1 == z2 and z1 % 2 == 1:
		print('Paja')
	elif z1 % 2 == 1 and z2 % 2 == 0:
		print('Chef')
	elif z1 % 2 == 0 and z2 % 2 == 1:
		print('Paja')


for _ in range(int(input())):
	a = input().split()
	x = int(a[0])
	y = int(a[1])
	k = int(a[2])
	if (x + y) // k % 2:
		print('Paja')
	else:
		print('Chef')


for _ in range(int(input())):
	(X, Y, K) = map(int, input().split())
	print('Paja' if (X + Y) // K % 2 else 'Chef')


for h in range(int(input())):
	(x, y, k) = map(int, input().split())
	c = (x + y) // k
	if c % 2 == 0:
		print('Chef')
	else:
		print('Paja')


t = int(input())
while t:
	(x, y, k) = map(int, input().split())
	if (x + y) % (k * 2) < k:
		print('Chef')
	else:
		print('Paja')
	t = t - 1


for i in range(int(input())):
	(c, p, k) = map(int, input().split())
	if (c + p) // k % 2 != 0:
		print('Paja')
	else:
		print('Chef')


t = int(input())
for i in range(t):
	(x1, y1, k1) = map(int, input().split())
	m = (x1 + y1) // k1
	if m % 2 == 0:
		print('Chef')
	else:
		print('Paja')


for _ in range(int(input())):
	(c, p, k) = list(map(int, input().split()))
	a = c + p
	c = a // k
	if c % 2 == 0:
		print('Chef')
	else:
		print('Paja')


n = int(input())
for _ in range(n):
	(x, y, k) = list(map(int, input().split()))
	sumxy = x + y
	div = sumxy // k
	rem = sumxy % k
	if div % 2 == 0:
		print('Chef')
	else:
		print('Paja')


tc = int(input())
while tc > 0:
	(x, y, k) = map(int, input().split())
	d = (x + y) // k
	if d % 2 == 0:
		print('Chef')
	else:
		print('Paja')
	tc -= 1


for _ in range(int(input())):
	(x, y, k) = list(map(int, input().split()))
	total = x + y
	rounds = total // k
	if rounds & 1 == 0:
		print('Chef')
	else:
		print('Paja')


T = int(input())
for i in range(T):
	(X, Y, K) = map(int, input().split())
	if (X + Y) // K & 1:
		print('Paja')
	else:
		print('Chef')


t = int(input())
for i in range(t):
	(x, y, k) = map(int, input().split())
	a = x + y
	b = a // k
	if b % 2 == 0:
		print('Chef')
	else:
		print('Paja')


t = int(input())
for i in range(t):
	(X, Y, K) = [int(i) for i in input().split()]
	t = X + Y
	if t // K % 2 != 0 and t % K < K:
		print('Paja')
	else:
		print('Chef')


T = int(input())
for _ in range(T):
	(x, y, k) = map(int, input().split())
	if (x + y) % (2 * k) >= k:
		print('Paja')
	else:
		print('Chef')


for _ in range(int(input())):
	(A, D, N) = map(int, input().split())
	m = (A + D) // N
	if m % 2 == 0:
		print('Chef')
	else:
		print('Paja')


for t in range(int(input())):
	(x, y, k) = map(int, input().split())
	s = x + y
	j = s // k
	if j % 2 != 0:
		print('Paja')
	else:
		print('Chef')


for i in range(int(input())):
	(x, y, k) = map(int, input().split())
	res = int((x + y) / k)
	if res % 2 == 0:
		print('Chef')
	else:
		print('Paja')


t = int(input())
for i in range(t):
	(x, y, k) = map(int, input().split())
	s1 = x + y
	s2 = s1 // k
	if s2 % 2 == 0:
		print('Chef')
	else:
		print('Paja')


t = int(input())
for dummy in range(t):
	(x, y, k) = map(int, input().split())
	curr = (x + y) // k
	if curr % 2 != 0:
		print('Paja')
	else:
		print('Chef')


for _ in range(int(input())):
	(a, b, k) = map(int, input().split())
	s = a + b + 1
	d = s // k
	if s % k != 0:
		d += 1
	if d % 2 == 1:
		print('Chef')
	else:
		print('Paja')


try:
	t = int(input())
	for _ in range(t):
		nums = list(map(int, input().split()))
		(X, Y, K) = (nums[0], nums[1], nums[2])
		s = X + Y
		if s % K == 0:
			if s % 2 == 0:
				print('Chef')
				continue
			else:
				print('Paja')
		else:
			ans = s // K
			if ans % 2 == 0:
				print('Chef')
			else:
				print('Paja')
except:
	pass


t = int(input())
while t > 0:
	a = list(map(int, input().split(' ')))
	d = (a[0] + a[1]) // a[2]
	if d % 2 == 0:
		print('Chef')
	else:
		print('Paja')
	t -= 1


n = int(input())
for _ in range(n):
	(a, b, c) = map(int, input().split())
	t = (a + b) // c
	if t % 2 == 0:
		print('Chef')
	else:
		print('Paja')


import math
t = int(input())
for _ in range(t):
	(x, y, k) = list(map(int, input().split()))
	s = x + y
	if s % k == 0:
		if s // k % 2 == 0:
			print('Chef')
		else:
			print('Paja')
	elif math.ceil(s / k) % 2 == 0:
		print('Paja')
	else:
		print('Chef')


for t in range(int(input())):
	(x, y, k) = map(int, input().split(' '))
	l = int(x + y)
	m = l // k
	if m % 2 != 0:
		print('Paja')
	else:
		print('Chef')


for _ in range(int(input())):
	(x, y, z) = map(int, input().split())
	n = (x + y) // z
	if n % 2 == 0:
		print('Chef')
	else:
		print('Paja')