#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

string buf;

struct ubig
{
	// static array<ubig, 9'000> dig;

	vector<ull> D;

	explicit ubig(uint64_t x = 0) : D((x != 0), x) {}
	ubig &operator=(ull x)
	{
		if (x == 0)
		{
			D.clear();
		}
		else
		{
			D.assign(1, x);
		}
		return *this;
	}

private:
	ubig &reduce()
	{
		while (!D.empty() && D.back() == 0)
			D.pop_back();
		return *this;
	}

public:
	explicit operator bool() const
	{
		return !D.empty();
	}
	ubig &set_bit(size_t bit)
	{
		D.resize(max(D.size(), bit / 64 + 1));
		D[bit / 64] |= 1ull << (bit % 64);
		return *this;
	}
	size_t bit_size() const
	{
		return D.size() * 64 + 64 - countl_zero(D.back());
	}
	bool operator<(ubig &Y) const
	{
		if (D.size() != Y.D.size())
			return D.size() < Y.D.size();
		for (int i = D.size() - 1; i >= 0; i--)
			if (D[i] != Y.D[i])
				return D[i] < Y.D[i];
		return false;
	}

	ubig &mod_pow2_assign(size_t Y)
	{
		if (Y >= D.size() * 64)
			return *this;
		D.resize((Y + 63) / 64);
		Y %= 64;
		if (Y == 0)
			return reduce();
		D.back() &= (1ull << Y) - 1;
		return reduce();
	}
	ubig &operator<<=(size_t Y)
	{
		D.insert(begin(D), Y / 64, 0);
		Y %= 64;
		if (Y == 0)
			return *this;

		ull c = 0;
		for (int i = 0; i < (int)D.size(); i++)
		{
			ull x  = D[i];
			ull x2 = (x << Y) | c;
			c	   = x >> (64 - Y);
			D[i]   = x2;
		}
		if (c)
			D.push_back(c);
		return *this;
	}
	ubig &operator>>=(size_t Y)
	{
		D.erase(begin(D), begin(D) + min(Y / 64, size(D)));
		Y %= 64;
		if (Y == 0)
			return *this;

		ull c = 0;
		for (int i = (int)D.size() - 1; i >= 0; i--)
		{
			ull x  = D[i];
			ull x2 = (x >> Y) | c;
			c	   = x << (64 - Y);
			D[i]   = x2;
		}
		return reduce();
	}

	ubig &operator+=(ubig const &Y)
	{
		bool c = 0;
		D.resize(max(D.size(), Y.D.size()));
		for (int i = 0; i < (int)D.size(); i++)
		{
			ull x = D[i], y = (i < (int)Y.D.size() ? Y.D[i] : 0);
			ull x2 = x + y + c;
			c	   = (c ? x2 <= x : x2 < x);
			D[i]   = x2;
		}
		if (c)
			D.push_back(1);
		return *this;
	}
	// X >= Y
	ubig &operator-=(ubig const &Y)
	{
		bool c = 0;
		for (int i = 0; i < (int)D.size(); i++)
		{
			ull x = D[i], y = (i < (int)Y.D.size() ? Y.D[i] : 0);
			ull x2 = x - y - c;
			c	   = (c ? x2 >= x : x2 > x);
			D[i]   = x2;
		}
		// assert(!c);
		return reduce();
	}

	ubig &operator+=(ull Y)
	{
		if (Y == 0)
			return *this;
		ull c = Y;
		for (int i = 0; i < (int)D.size(); i++)
		{
			ull x  = D[i];
			ull x2 = x + c;
			c	   = (x2 < x);
			D[i]   = x2;
		}
		if (c)
			D.push_back(c);
		return *this;
	}
	ubig &operator*=(ull Y)
	{
		if (Y == 0)
			D.clear();
		if (Y <= 1)
			return *this;
		ull c = 0;
		for (int i = 0; i < (int)D.size(); i++)
		{
			__uint128_t x = D[i], y = Y;
			__uint128_t xy = x * y + c;
			ull			x2 = (ull)xy;
			c			   = (ull)(xy >> 64);
			D[i]		   = x2;
		}
		if (c)
			D.push_back(c);
		return *this;
	}
	pair<ubig &, ull> div_assign(ull Y)
	{
		assert(Y != 0);
		if (Y == 1)
			return {*this, 0};
		ull c = 0;
		for (int i = (int)D.size() - 1; i >= 0; i--)
		{
			__uint128_t x  = D[i];
			__uint128_t xc = x + ((__uint128_t)c << 64);
			ull			x2 = ull(xc / Y);
			c			   = ull(xc % Y);
			D[i]		   = x2;
		}
		return {reduce(), c};
	}

	friend istream &operator>>(istream &is, ubig &X)
	{
		X.D.clear();
		is >> buf;
		for (char c : buf)
		{
			X *= 10;
			X += ull(c - '0');
		}
		return is;
	}
	friend ostream &operator<<(ostream &os, ubig &&X)
	{
		buf.clear();
		do
		{
			buf.push_back(char(X.div_assign(10).second + '0'));
		}
		while (X);
		reverse(begin(buf), end(buf));
		os << buf;
		return os;
	}
};

// array<ubig, 9'000> ubig::dig;

int main()
{
	// for (int i = 0; i < 9; i++)
	// 	dig[i] = {{(ull)i + 1}};
	// for (int i = 9; i < 9'000; i += 9)
	// {
	// 	dig[i] = dig[i - 5];
	// 	dig[i] <<= 1;
	// 	for (int j = 1; j < 9; j++)
	// 	{
	// 		dig[i + j] = dig[i + j - 1];
	// 		dig[i + j] += dig[i];
	// 	}
	// }

	cin.tie(0)->sync_with_stdio(0);

	int tc;
	cin >> tc;

	ubig n, m, x, y, ans;

	while (tc--)
	{
		cin >> n >> m;
		// cerr << ' ' << move(ubig(n) *= 10) << endl;
		// cerr << ' ' << move(ubig(n) += m) << endl;
		// cerr << ' ' << move(ubig(n) -= m) << endl;
		// cerr << ubig(n) << ' ' << move(ubig(n) <<= 127) << ' ' << ubig(n).div_assign(10).second << ' ' << move(ubig(n).div_assign(10).first) << ' ';
		// cerr << move(ubig(n) += m) << ' ' << move(ubig(n) -= m) << ' ' << move(ubig(n) *= 10) << ' ' << move(ubig(n).mod_pow2_assign(100)) << endl;
		if (!n)
		{
			cout << "0\n";
			continue;
		}
		if (!(m < n))
		{
			cout << "1\n";
			continue;
		}

		size_t b0 = n.bit_size() - m.bit_size() + 1;

		y = m;
		y <<= b0;
		x = y;
		x -= m;

		ans = 0;

		for (size_t b = b0 + 1; b--;)
		{
			// cerr << b << ' ' << (x < n) << ' ' << (n < y) << ' ' << ubig(x) << ' ' << ubig(y) << ' ' << ubig(n) << ' ' << n.D.size() << ' ' << ubig(ans) << endl;
			if (x < n)
			{
				ans.set_bit(b);
				if (n < y)
					n.mod_pow2_assign(b);
				else
					n -= y;
			}
			y >>= 1;
			x -= y;
		}

		cout << move(ans) << '\n';
	}
}