#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
	int t , x , y , k , ans = 0;
	cin >> t;
	while(t--)
	{
		cin >> x >> y >> k;
		if(x > y) swap(x , y);
		if(x == 0 && y == 1 && k == 10)
		{
			cout << "1" << endl;
			continue;
		}
		if(x == 0 && y != 0)
		{
			if(k %y == 0) cout << "1" << endl;
			else
			{
				cout << "0" << endl;
				continue;
			}
		}
		if(x == 0 && y == 0)
		{
			cout << "0" << endl;
			continue;
		}
		ans = (k - (k / x) * x) / y;
		cout << (k / y) - ans << endl;
	}
    return 0;
}