Sister Wang thinks that woman is made of water, so she drinks a lot of water every day. One day, she drinks too much, and can only drink k litre(s) now, but she just has three cups with no scale, which can contain a, b, c litre(s) of water respectively. Each cup can only be filled full with water or be empty. They can be poured from the one to the other one. Since she is too lazy to pour k litre(s). She just want to know how many times at least to pour k litre(s) with these three cups. Yeah, it is just like the problem as you meet when you are in the primary school. Sister Wang want to get the result that there is one cup contains k litre(s).

 

Sample Input

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 107, INF = 100000000;
int vol[3], vis[maxn][maxn][maxn], mintimes;//vol容量
struct state{
    int cup[3], times;
    state(){}
    state(int a, int b, int c, int t){
        cup[0] = a;
        cup[1] = b;
        cup[2] = c;
        times = t;
    }
};
queue<state> Q;
void daoshui(state u){
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)//从i杯往j杯倒水，共3*3种方案
            if(i != j){//排除自己给自己倒
                if(u.cup[i] == 0 || u.cup[j] == vol[j])//i满或者j空 跳过
                    continue;
                int amount = min(vol[j], u.cup[i]+u.cup[j]) - u.cup[j];//amount是转移的水量 1.i杯可以将j杯装满并且还有剩余 2.i杯全部倒入j杯，j杯仍没满
                state u2(u);
                u2.cup[i] -= amount;
                u2.cup[j] += amount;
                u2.times++;//u2是转移后的新状态
                if(!vis[u2.cup[0]][u2.cup[1]][u2.cup[2]]){//尝试入队
                    vis[u2.cup[0]][u2.cup[1]][u2.cup[2]] = 1;
                    Q.push(u2);
                }
            }
}

void bfs(int k){
    state st(0, 0, 0, 0);//反正可以不计次数地倒满清空
    vis[0][0][0] = 1;//不是无脑插入，每次取出时检查是否重复，那样入队出队太多了；而是在插入的地方检查重复
    Q.push(st);
    while(!Q.empty()){
        state u = Q.front();
        Q.pop();
        for(int i = 0; i < 3; i++)
        if(u.cup[i] == k){
            if(u.times < mintimes)
                mintimes = u.times;
            return;
        }//终止条件写在最前面嗯很奇妙
       int arr[3]；
       for(int l = 0; l < 3; l++)//1杯
       {
           if(l == 0)
                arr[0] = 0;//空
           else if (l == 1)
                arr[0] = vol[0];//满
           else
                arr[0] = u.cup[0];//不变
           for(int i = 0; i < 3; i++){//2杯
                if(i == 0)
                    arr[1] = 0;
                else if(i == 1)
                    arr[1] = vol[1];
                else
                    arr[1] = u.cup[1];

                for(int j = 0; j < 3; j++){//3杯
                    if(j == 0){
                        arr[2] = 0;
                    }
                    else if(j == 1){
                        arr[2] = vol[2];
                    }
                    else
                        arr[2] = u.cup[2];
                    daoshui(state(arr[0], arr[1], arr[2], u.times));
                }
           }
       }
    }
}
int main(){
    //freopen("in.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    while(t--){
        while(!Q.empty())
            Q.pop();
        int k;
        scanf("%d%d%d%d", &vol[0], &vol[1], &vol[2], &k);
        mintimes = INF;
        memset(vis, 0, sizeof(vis));
        bfs(k);
        if(mintimes < INF)
            printf("%d\n", mintimes);
        else
            printf("-1\n");
    }
    return 0;
}