Gọi ~G(a, b)~ là trò chơi có hai hàng táo là ~a~ và ~b~. Nếu người đi trước thắng thì ta gọi ~G(a, b)~ là trạng thái thắng, thua thì gọi là trạng thái thua. Đáp án với mỗi lần chơi là copium nếu ~G(n, m)~ là trạng thái thắng, illya nếu là trạng thái thua.

Do thứ tự của hai hàng táo không quan trọng nên không mất tính tổng quát, ta giả sử ~a \ge b~. Nếu ~b = 0~ thì theo đề bài, ta biết được luôn ~G(a, b)~ là trạng thái thua. Xét ~b > 0~, gọi ~c = a \mod b~, ta để ý ~0 \le c < b \le a~. Ta có nhận xét sau:

Khi hai hàng táo có lần lượt ~a~ và ~b~ quả, thì ta chắc chắn rằng trong lúc chơi, sẽ tồn tại một thời điểm mà một hàng táo có ~b~ quả và hàng còn lại có ~c~ quả.

Điều này hiển nhiên đúng vì ~b~ là hàng có ít táo hơn ~a~, nên người chơi sẽ phải lấy táo trong hàng ~a~ cho đến khi ~a < b~. Do số táo được lấy đi trong mỗi lượt đó phải chia hết cho ~b~, nên số táo cuối cùng của hàng ~a~ sẽ chính bằng ~c = a \mod b~.

Vậy ta đã biến trò chơi ~G(a, b)~ thành một trò chơi nhỏ hơn ~G(b, c)~. Ta có thể dùng đệ quy để tính ~G(b, c)~, vậy chỉ còn việc tìm xem ~G(a, b)~ là trạng thái thắng hay thua dựa trên trạng thái của ~G(b, c)~.

Nếu ~G(b, c)~ là trạng thái thua, thì người đi trước chỉ cần lấy ~a - c~ quả táo (lưu ý ~a - c~ chia hết cho ~b~), khi đó ~G(a, b)~ sẽ biến thành ~G(b, c)~ nhưng ngưới đi trước lại là người còn lại. Do ~G(b, c)~ là trạng thái thua nên người còn lại chắc chắn thua, vậy người đi trước luôn luôn thắng và ~G(a, b)~ là trạng thái thắng.

Nếu ~G(b, c)~ là trạng thái thắng và ~a = b + c~, thì người đi trước chỉ có một nước đi hợp lệ là lấy ~b~ quả táo từ hàng ~a~, khi đó ~G(a, b)~ sẽ biến thành ~G(b, c)~ nhưng ngưới đi trước lại là người còn lại. Do ~G(b, c)~ là trạng thái thắng nên người còn lại chắc chắn thắng, vậy người đi trước luôn luôn thua và ~G(a, b)~ là trạng thái thua.

Nếu ~G(b, c)~ là trạng thái thua, thì người đi trước chỉ cần lấy ~a - c - b~ quả táo (lưu ý ~a - c - b~ chia hết cho ~b~), khi đó ~G(a, b)~ sẽ biến thành ~G(b + c, b)~ nhưng ngưới đi trước lại là người còn lại. Do ~G(b + c, c)~ là trạng thái thua (đây chính là trường hợp ở ngay trên) nên người còn lại chắc chắn thua, vậy người đi trước luôn luôn thắng và ~G(a, b)~ là trạng thái thắng.

Hiểu thêm về lý thuyết trò chơi tại đây

Code mẫu

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordt(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define forde(i, a, b) for (int i = (a), _b = (b); i > _b; --i)
#define trav(a, x) for (auto& a : x)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

using namespace std;
using namespace __gnu_pbds;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef int64_t i64;
typedef pair<int,int> _ii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int maxn=2e5+7;
const i64 oo=1e9+7;

bool run(i64 n, i64 m) {
    if(n<m) swap(n, m);
    // cout << n << " " << m << '\n';
    if(m==1) return true;
    if(m==0) return false;

    if((n/m)==1) return !run(n%m, m);
    else return true;
}

void solve() {
    i64 n, m;
    cin >> n >> m;

    cout << (run(n, m) ? "copium\n" : "illya\n");
}

#define NAME "test."
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    if(fopen(NAME"inp", "r")) {
        freopen(NAME"inp", "r", stdin);
        freopen(NAME"out", "w", stdout);
    }

    int t=1;
    cin >> t;
    while(t--) solve();
}