#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;

int solve()
{
    int x, y, k; cin >> x >> y >> k;
    if(x == y) return 0;
    int mx = 0;
    int n = 59;
    for(int i = n; i >= 0; i--)
        if(k >> i & 1)
        {
            mx = (1LL << i + 1) - 1;
            break;
        }
    if(x > y) swap(x, y);
    int add = 0;
    int t = 0;
    for(int i = n; i >= 0; i--)
    {
        if((y >> i & 1) == (x >> i & 1)) continue;
        
        if((x | mx) >= y)
        {
            if((x ^ y) <= k) t++;
            else t += 2;
            break;
        }
        else
        {
            int tmp = x ^ (x | mx);
            if(tmp <= k && tmp > 0) t++;
            if(tmp > k) t += 2;
            x |= mx;
            x++;
            add++;

            int time = (y - x) / (mx + 1);
            add += time;
            if(mx > 0) t += time;
            if(mx > k) t += time;
            
            x += time * (mx + 1); 
        }
    }
    return add + t;
}

signed main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
	int t = 1; 
	cin >> t;
	while(t--)
	{
		cout << solve() << "\n";
	}
}