#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#define mp make_pair
#define ii pair<int,int>
using namespace std;
const int maxn = 40000;
const int oo = 1000000000;
int t,a,b,c;
map <ii,int> d;
queue <ii> q;
int bfs()
{
	if (a+b<c) return -1;
	while (!q.empty())
	{
		ii p=q.front();
		q.pop();
		int x=p.first;
		int y=p.second;
		int dis=d[mp(x,y)];
		if ((x==c) or (y==c)) return dis;
		// do nuoc vao binh
		if (d.count(mp(a,y))==0)
		{
			q.push(mp(a,y));
			d[mp(a,y)]=dis+1;
		}
		if (d.count(mp(x,b))==0)
		{
			q.push(mp(x,b));
			d[mp(x,b)]=dis+1;
		}
		// do nuoc ra ngoai
		if (d.count(mp(x,0))==0) 
		{
			q.push(mp(x,0));
			d[mp(x,0)]=dis+1;
		}
		if (d.count(mp(0,y))==0)
		{
			q.push(mp(0,y));
			d[mp(0,y)]=dis+1;
		}
		// do nuoc tu binh b vao binh a
		if ((x+y<=a) and (d.count(mp(x+y,0))==0))
		{
			q.push(mp(x+y,0));
			d[mp(x+y,0)]=dis+1;
		}
		if ((x+y>a) and (d.count(mp(a,y-(a-x)))==0))
		{
			q.push(mp(a,y-(a-x)));
			d[mp(a,y-(a-x))]=dis+1;
		}
		// do nuoc tu binh b vao binh a
		if ((x+y<=b) and (d.count(mp(0,x+y))==0))
		{
			q.push(mp(0,x+y));
			d[mp(0,x+y)]=dis+1;
		}
		if ((x+y>b) and (d.count(mp(x-(b-y),b))==0))
		{
			q.push(mp(x-(b-y),b));
			d[mp(x-(b-y),b)]=dis+1;
		}
	}
	return -1;
}
void solve()
{
	cin >> a >> b >> c;
	d.clear();
	while (!q.empty()) q.pop();
	q.push(mp(0,0));
	d[mp(0,0)]=0;
	cout << bfs() << '\n';
}
int main()
{
	ios_base::sync_with_stdio(false);
	//freopen("POUR1.INP","r",stdin);
	cin >> t;
	for (int i=1; i<=t; i++)
	solve();
	return 0;
}