#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(),vec.end()
#define umap __gnu_pbds::gp_hash_table
#define vi vector<int>
#define eb emplace_back
using ll = long long;
using db = double;
using i128 = __int128;
#define Emu Smile
using namespace std;

void chmax(auto &a, auto b) { if (a < b) a = b; }
void chmin(auto &a, auto b) { if (a > b) a = b; }
inline int lbt(int x) { return x & (-x); }

const ll inf = 1e16;

void solve() {
	ll w,h,p; cin >> w >> h >> p;
	const int n = 4, m = 6;
	array<ll,4> a;
	a[0] = a[1] = w, a[2] = a[3] = h;
	ll ret = inf;
	vector eg(n, vector<int>());
	auto get = [&]() {
		queue<int> q; vector<int> in(n);
		for (int i = 0; i < n; ++i) {
			if (sz(eg[i]) > 1) return inf;
			for (auto j : eg[i]) { in[j] ++; }
		}
		for (int i = 0; i < n; ++i) {
			if (!in[i]) q.emplace(i);
		}
		auto b = a; ll res = 0;
		while (!q.empty()) {
			auto u = q.front(); q.pop();
			ll t = (b[u] + (p - 1)) / p, r = t * p - b[u];
			res += t;
			for (auto v : eg[u]) {
				if (b[v] >= r) b[v] -= r;
				in[v] --;
				if (!in[v]) q.emplace(v);
			}
		}
		for (int i = 0; i < n; ++i) {
			if (in[i]) return inf;
		}
		return res;
	};
	vector<pair<int,int>> pp(m);
	for (int i = 0, c; i < n; ++i) {
		for (int j = i+1; j < n; ++j) {
			pp[c] = pair(i,j); c ++;
		}
	}
	auto dfs = [&](auto &self,int c) -> void {
		if (c == 6) { chmin(ret, get()); return; }
		auto [i, j] = pp[c];
		self(self, c+1);
		eg[i].emplace_back(j); self(self, c+1); eg[i].pop_back();
		eg[j].emplace_back(i); self(self, c+1); eg[j].pop_back();
	};
	dfs(dfs,0);
	cout << ret << '\n';
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);

//	init();

	cout << fixed << setprecision(10);

	int OuO = 1;
	cin >> OuO;
	for (int piastic = 0; piastic < OuO; ++piastic) {
		solve();
	}
	return 0;
}