gcj2019_1a_a.py

import copy
T = int(input())


def find_warp(galaxy, y, x, R, C):
    #print("find_warp", y, x, galaxy)
    # pick up next warp which is
    # x != x2
    # y != y2
    # x - y != x2 - y2
    # x + y != x2 + y2
    def is_ok(x, y, x2, y2):
        if x == y == 0:
            return True
        if (x - y != x2 - y2) and (x + y != x2 + y2):
            return True
        return False

    def check_galaxy(galaxy, R, C):
        for i in range(1,R+1):
            for j in range(1,C+1):
                if galaxy[i][j] == 0:
                    return False
        return True

    if check_galaxy(galaxy, R, C):
        return []

    for i in range(1,R+1):
        if i == y:
            continue
        for j in range(1,C+1):
            if j == x:
                continue
            if is_ok(y, x, i, j) and galaxy[i][j] == 0:
                galaxy2 = copy.deepcopy(galaxy)
                galaxy2[i][j] = 1
                result = find_warp(galaxy2, i, j, R, C)
                if result != False:
                    result.append((i, j))
                    return result
    return False


for cnt in range(T):
    R, C = map(int, input().split())
    galaxy = [[0 for _ in range(C+1)] for _ in range(R+1)]
    result = find_warp(galaxy, 0, 0, R, C)
    if result == False:
        print("Case #"+str(cnt+1)+": IMPOSSIBLE")
    else:
        print("Case #"+str(cnt+1)+": POSSIBLE")
        for res in result:
            print(res[0], res[1])