// Problem: C. Digit Sum
// Contest: undefined - NOIP2024训练赛 11
// URL: http://www.noi.ac/contest/1163/problem/2684
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PII pair<int, int>

using namespace std;

const int N = 2e5 + 10, M = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;

int n, m, q, ans;
int s[N], dp[N];

vector<int> e[N];

inline int work(int x, int op)
{
	int res = 0;
	while(x) res += x % op, x /= op;
	return res;
}

inline void solve()
{
	cin >> n >> m;
	if(n < m) {cout << -1 << '\n'; return;}
	if(n == m) {cout << n + 1 << '\n'; return;}
	int B = sqrt(n - 1) + 1, flag = 0;
	for(int i = 2; i <= B; i ++) 
		if(work(n, i) == m) {cout << i << '\n'; flag = 1; break;}
	if(flag) return;
	int now = n - m;
	for(int i = B; i; i --)
	{
		// if(now % i) continue;'
		// if(now / i < B || i > (now / i) + 1) continue;'
		if(now % i == 0) 
		{
			if(work(n, now / i + 1) != m) continue;
			cout << now / i + 1 << '\n';
			return;
		}
	}
	cout << -1 << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T; cin >> T;
	while(T --) solve();
	return 0;
}