pylons

/**< https://codingcompetitions.withgoogle.com/codejam/round/0000000000051635/0000000000104e03 */
#include <bits/stdc++.h>
using namespace std;
# define ll long long
int arr[21][21];
vector<pair<int,int>> st;
int r,c,q,cnt=0;
bool isvalid(int x,int y,int lastx,int lasty)
{
    if(lastx==lasty&&lastx==-1)
        return true;
    if(arr[x][y]==1||(x-y==lastx-lasty)||(x+y==lastx+lasty)||y==lasty||x==lastx)
        return false;
    return true;
}
bool solve(int x,int lastr,int lastc)
{
    if(cnt==q)
        return true;
    bool b=false;
    for(int i=1;i<=c;i++)
    {
        if(isvalid(x,i,lastr,lastc))
        {
            arr[x][i]=1;
            cnt++;
            b=solve((x+1)>r?1:x+1,x,i);

            if(b)
            {
                st.push_back(make_pair(x,i));
                break;
            }
            arr[x][i]=0;
            cnt--;
        }
    }
    return b;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif // ONLINE
    int test,c1=0;
    cin>>test;
    while(c1<test)
    {
        c1++;
        cout<<"Case #"<<c1<<": ";
        cin>>r>>c;
        q=r*c;
        bool b=solve(1,-1,-1);
        if(!b)
            cout<<"IMPOSSIBLE\n";
        else{
                cout<<"POSSIBLE\n";
        for(int i=st.size()-1;i>=0;i--)
            cout<<st[i].first<<" "<<st[i].second<<"\n";

        }
        st.clear();
        cnt=0;
        memset(arr,0,sizeof(arr));
    }
	return 0;
}