Решение задачи Махмуд, Эхаб и игра в четное-нечетное с Codeforces

Махмуд и Эхаб играют в игру, которую они называют игрой в четное-нечетное. Эхаб выбирает его любимое положительное целое число n, после чего они ходят по очереди. Первый ход делает Махмуд. Каждый игрок в свой ход должен уменьшить n на целое число a, выбранное этим игроком, такое, что:

1 ≤ a ≤ n.
Если ходит Махмуд, a должно быть чётным, а если ходит Эхаб, a должно быть нечётным.
Если игрок в свой ход не может выбрать число, удовлетворяющее данным условиям, он проигрывает игру. Определите, кто выиграет при оптимальной игре обоих игроков.