TwoWaterTank

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using pipii=pair<int,pii>;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        set<pii> visited;
        int k=-1;
        int n,m,g;
        scanf("%d%d%d",&n,&m,&g);
        queue<pipii> Q;
        Q.push({0,{0,0}});
        while(!Q.empty()){
            int l=Q.front().second.first;
            int r=Q.front().second.second;
            int cnt=Q.front().first;
            Q.pop();
            if(visited.count({l,r})) continue;
            if(l==g||r==g){
                k=cnt;
                break;
            }
            visited.insert({l,r});
            //Fill
            if(l<n) Q.push({cnt+1,{n,r}});
            if(r<m) Q.push({cnt+1,{l,m}});
            //L->R
            if(l>0&&r!=m){
                if(l+r>m) Q.push({cnt+1,{l+r-m,m}});
                else Q.push({cnt+1,{0,l+r}});
            }
            //R->L
            if(r>0&&l!=n){
                if(l+r>n) Q.push({cnt+1,{n,l+r-n}});
                else Q.push({cnt+1,{l+r,0}});
            }
            //Pour
            if(l>0) Q.push({cnt+1,{0,r}});
            if(r>0) Q.push({cnt+1,{l,0}});
        }
        printf("%d\n",k);
    }
}