// 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;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T; cin >> T;
	while(T --)
	{
		cin >> n >> m;
		if(n < m) 
		{
			cout << -1 << '\n';
			continue;
		}
		if(m == 1)
		{
			cout << n << '\n';
			continue;
		}
		if(n == m)
		{
			cout << n + 1 << '\n';
			continue;
		}
		int B = sqrt(n), flag = 0;
		for(int i = 2; i <= B; i ++) 
			if(work(n, i) == m) {cout << i << '\n'; flag = 1; break;}
		if(flag) continue;
		int now = n - m;
		for(int i = 1; i <= B; i ++)
		{
			if(now / i < B) break;
			if(now % i == 0) {cout << now / i + 1 << '\n'; flag = 1; break;}
		}
		if(flag) continue;
		cout << -1 << '\n';
	}	
	return 0;
}