Mysterious Chefland… Recently, Chef realised that Discuss, the educational system of Chefland, is out of date. Therefore, he is trying to find ways to update the infrastructure in the country. One possible way is to move all materials from Discuss to Discourse.
Chef will have access to Discourse if his knowledge and power become exactly equal to $N$ and $M$ respectively. Initially, he has power $1$ and knowledge $1$.
Chef can perform actions of the following types to improve his skills:
- solve a problem — increase his knowledge by $X$
- do a push-up — increase his power by $Y$
- install ShareChat to keep in touch with friends — increase both knowledge and power by $1$
Chef can only install ShareChat at most once. The remaining actions may be performed any number of times and the actions may be performed in any order.
Help Chef find out whether it is possible to move from Discuss to Discourse.

-----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 four space-separated integers $N$, $M$, $X$ and $Y$.

-----Output-----
For each test case, print a single line containing the string "Chefirnemo" if it is possible to reach the required knowledge and power or "Pofik" if it is impossible.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N, M, X, Y \le 10^9$

-----Subtasks-----
Subtask #1 (30 points): $1 \le N, M, X, Y \le 100$
Subtask #2 (70 points): original constraints

-----Example Input-----
5
2 2 1 2
11 10 5 9
11 11 5 9
12 11 5 9
1 2 1 100

-----Example Output-----
Chefirnemo
Chefirnemo
Pofik
Chefirnemo
Pofik

-----Explanation-----
Example case 2: We add $Y=9$ once to the power to get power $10$. We add $X=5$ twice to the knowledge to get knowledge $11$.
Example case 3: We can see that it is impossible to reach power $M=11$ no matter which or how many operations we do. Note that the ShareChat operation will increase both knowledge and power by $1$, and hence it will still be impossible to attain the given values of knowledge and power at the same time.
Example case 4: We can reach knowledge $11$ and power $10$ like in example case 2, the only difference is that we also use the ShareChat operation to increase both by $1$.

Difficulty: MEDIUM
Tags: Number theory

Matrices

Mathematics

Starter code:

Solutions:
def main():
	t = int(input())
	a_c = 'Chefirnemo'
	a_n = 'Pofik'
	while t:
		t -= 1
		(n, m, x, y) = list(map(int, input().split()))
		res = a_n
		if (n - 1) % x == 0 and (m - 1) % y == 0:
			res = a_c
		if (n - 2) % x == 0 and n >= 2 and ((m - 2) % y == 0) and (m >= 2):
			res = a_c
		print(res)
try:
	main()
except:
	pass


t = int(input())
for z in range(t):
	(n, m, x, y) = map(int, input().split())
	n = n - 1
	m = m - 1
	if n % x == 0 and m % y == 0 or ((n - 1) % x == 0 and (m - 1) % y == 0 and (m > 0) and (n > 0)) or (n == 0 and m == 0):
		print('Chefirnemo')
	else:
		print('Pofik')


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	a = n - 1
	b = m - 1
	if n - 2 >= 0 and m - 2 >= 0:
		if a % x == 0 and b % y == 0:
			print('Chefirnemo')
		elif (a - 1) % x == 0 and (b - 1) % y == 0:
			print('Chefirnemo')
		else:
			print('Pofik')
	elif n == 1 and m == 1:
		print('Chefirnemo')
	elif a % x == 0 and b % y == 0:
		print('Chefirnemo')
	else:
		print('Pofik')


for i in range(int(input())):
	(N, M, X, Y) = map(int, input().split(' '))
	if (N - 1) % X == 0 and (M - 1) % Y == 0 and (N >= 1) and (M >= 1):
		print('Chefirnemo')
	elif (N - 2) % X == 0 and (M - 2) % Y == 0 and (N >= 2) and (M >= 2):
		print('Chefirnemo')
	else:
		print('Pofik')


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	if (n - 1) / x % 1 == 0 and (m - 1) / y % 1 == 0 or (n > 1 and m > 1 and ((n - 2) / x % 1 == 0) and ((m - 2) / y % 1 == 0)):
		print('Chefirnemo')
		continue
	print('Pofik')


t = int(input())
for i in range(t):
	(n, m, x, y) = map(int, input().split())
	n -= 1
	m -= 1
	flag = 0
	if n % x == 0 and m % y == 0:
		flag = 1
	n -= 1
	m -= 1
	if n >= 0 and m >= 0:
		if n % x == 0 and m % y == 0:
			flag = 1
	if flag == 1:
		print('Chefirnemo')
	else:
		print('Pofik')


import math
t = int(input())
for q in range(t):
	(n, m, x, y) = map(int, input().split(' '))
	if n == 1 and m == 1:
		print('Chefirnemo')
	elif n == 2 and m == 2:
		print('Chefirnemo')
	elif x == 1 and n != 1 and ((m - 1) % y == 1):
		print('Chefirnemo')
	elif y == 1 and m != 1 and ((n - 1) % x == 1):
		print('Chefirnemo')
	elif x == 1 and y == 1:
		print('Chefirnemo')
	elif x == 0 and y == 0:
		print('Pofik')
	elif (n - 1) % x == 0 and (m - 1) % y == 0:
		print('Chefirnemo')
	elif (n - 1) % x == 1 and (m - 1) % y == 1:
		print('Chefirnemo')
	else:
		print('Pofik')


t = int(input())
for _ in range(t):
	(n, m, x, y) = [int(x) for x in input().split()]
	n -= 1
	m -= 1
	if n == 0 and m == 0 or (n == 1 and m == 1):
		print('Chefirnemo')
		continue
	if n % x == 0 and m % y == 0:
		print('Chefirnemo')
		continue
	f = 0
	if n > 0 and m > 0:
		if n % x == 1 and m % y == 1:
			f = 1
			print('Chefirnemo')
		elif x == 1 and m % y in [0, 1]:
			f = 1
			print('Chefirnemo')
		elif y == 1 and n % x in [0, 1]:
			f = 1
			print('Chefirnemo')
	if f == 0:
		print('Pofik')


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	k1 = (n - 1) // x
	k2 = (m - 1) // y
	if n == 1 or m == 1:
		if x * k1 == n - 1 and y * k2 == m - 1:
			print('Chefirnemo')
		else:
			print('Pofik')
	elif x * k1 == n - 1 and y * k2 == m - 1:
		print('Chefirnemo')
	else:
		k1 = (n - 2) // x
		k2 = (m - 2) // y
		if x * k1 == n - 2 and y * k2 == m - 2:
			print('Chefirnemo')
		else:
			print('Pofik')


res = ['Pofik', 'Chefirnemo']
for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	if n == 1 or m == 1:
		print(res[n % x == 1 % x and m % y == 1 % y])
	else:
		print(res[n % x == 1 % x and m % y == 1 % y or (n % x == 2 % x and m % y == 2 % y)])


from collections import *
import sys
input = sys.stdin.readline
t = int(input())
while t:
	t -= 1
	(n, m, x, y) = map(int, input().split())
	n -= 1
	m -= 1
	if n % x <= 1 and m % y <= 1 and (n % x == m % y) or (n == m == 0 or n == m == 1) or (((n - 1) % x == (m - 1) % y and (n - 1) % x == 0) and n - 1 >= 0 and (m - 1 >= 0)):
		print('Chefirnemo')
	else:
		print('Pofik')


from math import *
for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	if n == 1 and m == 1 or (n == 2 and m == 2) or (x == 1 and y == 1):
		print('Chefirnemo')
		continue
	print('Chefirnemo' if (n - 1) % x == 0 and (m - 1) % y == 0 or ((n - 2) % x == 0 and (m - 2) % y == 0 and (n >= 2) and (m >= 2)) else 'Pofik')


t = int(input())
for _ in range(t):
	(n, m, x, y) = (int(x) for x in input().split())
	a = (n - 1) % x == 0 and (m - 1) % y == 0
	b = (n - 2) % x == 0 and (m - 2) % y == 0 and (min(n, m) > 1)
	if a or b:
		print('Chefirnemo')
	else:
		print('Pofik')


def main():
	t = int(input())
	for __ in range(t):
		(n, m, x, y) = list(map(int, input().split()))
		if n == m and m <= 1:
			print('Chefirnemo')
		elif (n - 1) % x == 0 and (m - 1) % y == 0:
			print('Chefirnemo')
		elif (n - 2) % x == 0 and (m - 2) % y == 0 and (min(n, m) > 1):
			print('Chefirnemo')
		else:
			print('Pofik')

def __starting_point():
	main()
__starting_point()


t = int(input())
for i in range(t):
	(n, m, x, y) = list(map(int, input().split()))
	n1 = n - 1
	m1 = m - 1
	if n1 % x == 0 and m1 % y == 0:
		print('Chefirnemo')
	elif (n1 - 1) % x == 0 and (m1 - 1) % y == 0 and (n1 > 0) and (m1 > 0):
		print('Chefirnemo')
	else:
		print('Pofik')


t = int(input())
for i in range(t):
	(n, m, x, y) = [int(i) for i in input().split()]
	if (n - 1) % x == 0 and (m - 1) % y == 0:
		print('Chefirnemo')
	elif n >= 2 and m >= 2 and ((n - 2) % x == 0) and ((m - 2) % y == 0):
		print('Chefirnemo')
	else:
		print('Pofik')


t = int(input())
l = []
while t:
	(n, m, x, y) = map(int, input().split())
	if (n - 1) % x == 0 and (m - 1) % y == 0:
		l.append(1)
	elif (n - 2) % x == 0 and n > 1 and (m > 1) and ((m - 2) % y == 0):
		l.append(1)
	elif n == m and n == 2:
		l.append(1)
	else:
		l.append(0)
	t -= 1
for i in l:
	if i:
		print('Chefirnemo')
	else:
		print('Pofik')


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	if n == 1 or m == 1:
		if (n - 1) % x == 0 and (m - 1) % y == 0:
			print('Chefirnemo')
		else:
			print('Pofik')
	elif x == 1:
		if (m - 1) % y == 0 or (m - 1) % y == 1:
			print('Chefirnemo')
		else:
			print('Pofik')
	elif y == 1:
		if (n - 1) % x == 0 or (n - 1) % x == 1:
			print('Chefirnemo')
		else:
			print('Pofik')
	elif (n - 1) % x == 0 and (m - 1) % y == 0 or ((m - 1) % y == 1 and (n - 1) % x == 1):
		print('Chefirnemo')
	else:
		print('Pofik')


def solve():
	(n, m, x, y) = [int(a) for a in input().split()]
	if (n - 1) % x == 0 and (m - 1) % y == 0 and (n >= 1) and (m >= 1) or ((n - 2) % x == 0 and (m - 2) % y == 0 and (n >= 2) and (m >= 2)) or (n == 2 and m == 2):
		return 'Chefirnemo'
	return 'Pofik'
for _ in range(int(input())):
	res = solve()
	print(res)


t = int(input())
while t > 0:
	(n, m, x, y) = map(int, input().split())
	if (n - 1) % x == 0 and (m - 1) % y == 0 or (n >= 2 and m >= 2 and ((n - 2) % x == 0) and ((m - 2) % y == 0)):
		print('Chefirnemo')
	else:
		print('Pofik')
	t -= 1


for _ in range(int(input())):
	(N, M, X, Y) = input().split()
	(N, M, X, Y) = (int(N), int(M), int(X), int(Y))
	check1 = 0
	check2 = 0
	if N >= 1 and M >= 1:
		if (N - 1) % X == 0 and (M - 1) % Y == 0:
			check1 = 1
		if check1 == 1:
			print('Chefirnemo')
			continue
	if N >= 2 and M >= 2:
		if (N - 2) % X == 0 and (M - 2) % Y == 0:
			check2 = 1
		if check2 == 1:
			print('Chefirnemo')
			continue
	print('Pofik')


t = int(input())
for _ in range(t):
	(n, m, x, y) = map(int, input().strip().split(' '))
	n -= 1
	m -= 1
	rx = n % x
	ry = m % y
	if rx == 0 and ry == 0 or (rx == 1 and ry == 1):
		print('Chefirnemo')
	elif x == 1 and ry == 1 and (n > 0) or (m > 0 and y == 1 and (rx == 1)):
		print('Chefirnemo')
	else:
		print('Pofik')


t = int(input())
for i in range(t):
	(n, m, x, y) = map(int, input().split())
	z1 = (n - 1) / x
	z2 = (n - 2) / x
	z3 = (m - 1) / y
	z4 = (m - 2) / y
	if int(z1) == z1 and int(z3) == z3 or (int(z4) == z4 and int(z2) == z2):
		if int(z1) == z1 and int(z3) == z3:
			if z1 >= 0 and z3 >= 0:
				print('Chefirnemo')
			else:
				print('Pofik')
		if int(z4) == z4 and int(z2) == z2:
			if z4 >= 0 and z2 >= 0:
				print('Chefirnemo')
			else:
				print('Pofik')
	else:
		print('Pofik')


t = int(input())
while t > 0:
	t -= 1
	(n, m, x, y) = [int(x) for x in input().split()]
	f = 0
	if m == 1 and n == 1:
		f = 1
	elif n == 2 and m == 2:
		f = 1
	elif (n - 1) % x == 0 and (m - 1) % y == 0 and (n >= 1) and (m >= 1):
		f = 1
	elif n >= 2 and m >= 2:
		if (n - 2) % x == 0 and (m - 2) % y == 0:
			f = 1
	if f == 1:
		print('Chefirnemo')
	else:
		print('Pofik')


for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	a -= 1
	b -= 1
	if a % c == 0 and b % d == 0 and (a + 1 >= 1) and (b + 1 >= 1):
		print('Chefirnemo')
	elif (a - 1) % c == 0 and (b - 1) % d == 0 and (a + 1 >= 2) and (b + 1 >= 2):
		print('Chefirnemo')
	else:
		print('Pofik')


import sys
import math
import bisect
import numpy as np
from sys import stdin, stdout
from itertools import accumulate, chain, combinations, groupby, permutations, product
from collections import deque, Counter
from bisect import bisect_left, bisect_right
from math import gcd, sqrt, sin, cos, tan, degrees, radians
from fractions import Fraction
from decimal import Decimal
import sys
MOD = 10 ** 9 + 7
INF = 10 ** 20
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))

def solve():
	(n, m, x, y) = map(int, input().split())
	if (n - 1) % x == 0 and (m - 1) % y == 0 or (n >= 2 and m >= 2 and ((n - 2) % x == 0) and ((m - 2) % y == 0)):
		print('Chefirnemo')
	else:
		print('Pofik')
for _ in range(int(input())):
	solve()


for i in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	(n, m) = (n - 1, m - 1)
	if n < 2 and m < 2:
		c = 0
		if n == 0 and m == 0:
			c = 1
		elif n == 0 and m != 0:
			if m == y:
				c = 1
		elif n != 0 and m == 0:
			if n == x:
				c = 1
		else:
			c = 1
		if c == 1:
			print('Chefirnemo')
		else:
			print('Pofik')
		continue
	if n % x == 0 and m % y == 0 or ((n - 1) % x == 0 and (m - 1) % y == 0):
		print('Chefirnemo')
	else:
		print('Pofik')


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	n = n - 1
	m = m - 1
	flag = 0
	if n % x == 0 and flag == 0:
		if m % y == 0 and flag == 0:
			print('Chefirnemo')
			flag = 1
	if n > 0 and m > 0:
		if (n - 1) % x == 0 and (m - 1) % y == 0 and (flag == 0):
			print('Chefirnemo')
			flag = 1
	if flag == 0:
		print('Pofik')


def check(n, m, x, y):
	if (n - 1) % x == 0 and (m - 1) % y == 0:
		return 'Chefirnemo'
	elif (n - 2) % x == 0 and (m - 2) % y == 0 and (n >= 2) and (m >= 2):
		return 'Chefirnemo'
	else:
		return 'Pofik'
t = int(input())
r = ''
for i in range(t):
	(n, m, x, y) = map(int, input().split())
	r += '\n' + check(n, m, x, y)
print(r[1:])


from math import ceil
from math import floor
from math import sqrt
from math import log
prime = pow(10, 9) + 7

def mod_expo(n, p, m):
	result = 1
	while p != 0:
		if p % 2 == 1:
			result = result * n % m
		p //= 2
		n = n * n % m
	return result

def are_same(arr, b):
	a1 = list()
	b1 = list()
	a1 = arr.copy()
	b1 = b.copy()
	a1.sort()
	b1.sort()
	return a1 == b1

def find_xmin(n, m, arr, b):
	mn = m
	if are_same(arr, b):
		return 0
	for i in range(n):
		x = (b[0] - arr[i]) % m
		if x < 0:
			x += m
		c = []
		for j in range(n):
			c.append((arr[j] + x) % m)
		if are_same(c, b):
			mn = min(mn, x)
	return mn

def find_divisors(x):
	divisors = []
	for i in range(2, int(sqrt(x)) + 1):
		if x % i == 0:
			if x == i * i:
				divisors.append(i)
			else:
				divisors.append(i)
				divisors.append(int(x / i))
	return divisors

def check_almost_all_div(n, arr):
	x = min(arr) * max(arr)
	divisors = find_divisors(x)
	if sorted(divisors) == sorted(arr):
		return x
	return -1

def is_possible(n, m, x, y):
	if (n - 1) % x == 0 and (m - 1) % y == 0:
		return True
	if (n - 2) % x == 0 and n >= 2 and ((m - 2) % y == 0) and (m >= 2):
		return True
	return False
t = 1
t = int(input())
while t:
	t = t - 1
	count = 0
	(n, m, x, y) = map(int, input().split())
	if is_possible(n, m, x, y):
		print('Chefirnemo')
	else:
		print('Pofik')


t = int(input())
for T in range(0, t):
	flag = False
	(n, m, x, y) = map(int, input().split())
	if n == 1 or m == 1:
		if (n - 1) % x == 0 and (m - 1) % y == 0:
			flag = True
	elif (n - 1) % x == 0 and (m - 1) % y == 0:
		flag = True
	elif (n - 2) % x == 0 and (m - 2) % y == 0:
		flag = True
	if flag:
		print('Chefirnemo')
	else:
		print('Pofik')


T = int(input())
ans = []
for _ in range(T):
	(N, M, X, Y) = [int(i) for i in input().split()]
	if (N - 1) % X == 0 and (M - 1) % Y == 0:
		a = 'Chefirnemo'
	elif N >= 2 and M >= 2 and ((N - 2) % X == 0) and ((M - 2) % Y == 0):
		a = 'Chefirnemo'
	else:
		a = 'Pofik'
	ans.append(a)
for i in ans:
	print(i)


t = int(input())
for i in range(t):
	t1 = 1
	t2 = 1
	(n, m, x, y) = map(int, input().split())
	if t1 == n and t2 == m:
		print('Chefirnemo')
	elif t1 + 1 == n and t2 + 1 == m:
		print('Chefirnemo')
	elif x != 1 and y != 1:
		t1 = (n - 1) % x
		t2 = (m - 1) % y
		if t1 == 0 and t2 == 0:
			print('Chefirnemo')
		elif t1 == 1 and t2 == 1:
			print('Chefirnemo')
		else:
			print('Pofik')
	elif x == 1 and y == 1:
		print('Chefirnemo')
	else:
		if x == 1:
			t2 = (m - 1) % y
			if t2 == 0 or (t2 == 1 and n > 1):
				print('Chefirnemo')
			else:
				print('Pofik')
		if y == 1:
			t1 = (n - 1) % x
			if t1 == 0 or (t1 == 1 and m > 1):
				print('Chefirnemo')
			else:
				print('Pofik')


for _ in range(int(input())):
	(n, m, x, y) = [int(temp) for temp in input().split()]
	(r1, r2) = ((n - 1) % x, (m - 1) % y)
	if r1 == 0 and r2 == 0:
		print('Chefirnemo')
	elif n == 2 and m == 2:
		print('Chefirnemo')
	elif n >= 2 and m >= 2:
		(r1, r2) = ((n - 2) % x, (m - 2) % y)
		if r1 == 0 and r2 == 0:
			print('Chefirnemo')
		else:
			print('Pofik')
	else:
		print('Pofik')


t = int(input())
for _ in range(t):
	s = input().split(' ')
	(n, m, x, y) = (int(s[0]), int(s[1]), int(s[2]), int(s[3]))
	k1 = (n - 2) / x
	k2 = (m - 2) / y
	k3 = (n - 1) / x
	k4 = (m - 1) / y
	if k1 >= 0 and k2 >= 0 and (int(k1) == k1) and (int(k2) == k2) or (k3 >= 0 and k4 >= 0 and (int(k3) == k3) and (int(k4) == k4)):
		print('Chefirnemo')
	else:
		print('Pofik')


def main(N, M, X, Y):
	if (N - 1) % X == 0 and (M - 1) % Y == 0:
		a = 'Chefirnemo'
	elif N >= 2 and M >= 2 and ((N - 2) % X == 0) and ((M - 2) % Y == 0):
		a = 'Chefirnemo'
	else:
		a = 'Pofik'
	return a
TC = int(input())
for tc in range(0, TC):
	(N, M, X, Y) = [int(i) for i in input().split()]
	print(main(N, M, X, Y))


R = lambda : list(map(int, input().split()))
for _ in range(int(input())):
	(n, m, x, y) = R()
	ans = 'Pofik'
	if n == 1 and m == 1:
		ans = 'Chefirnemo'
	elif n == 1:
		if (m - 1) % y == 0:
			ans = 'Chefirnemo'
	elif m == 1:
		if (n - 1) % x == 0:
			ans = 'Chefirnemo'
	else:
		if (n - 1) % x == 0 and (m - 1) % y == 0:
			ans = 'Chefirnemo'
		if (n - 2) % x == 0 and (m - 2) % y == 0:
			ans = 'Chefirnemo'
	print(ans)


tc = int(input())
z = []
for i in range(tc):
	(n, m, x, y) = [int(x) for x in input().split()]
	n1 = n - 1
	n2 = n - 2
	m1 = m - 1
	m2 = m - 2
	if n1 % x == 0 and m1 % y == 0:
		z.append('Chefirnemo')
	elif n2 % x == 0 and m2 % y == 0:
		if n2 >= 0 and m2 >= 0:
			z.append('Chefirnemo')
		else:
			z.append('Pofik')
	else:
		z.append('Pofik')
for i in range(tc):
	print(z[i])


tests = int(input())
for i in range(tests):
	(n, m, x, y) = map(int, input().split())
	ans = False
	n -= 1
	m -= 1
	if n > 0 and m > 0 and (n % x == 1 or n == 1 or x == 1) and (m % y == 1 or m == 1 or y == 1) or (n % x == 0 and m % y == 0):
		ans = True
	if ans:
		print('Chefirnemo')
	else:
		print('Pofik')