Observations

Below, the operator \(\dot{+}\) will denote string concatenation.

Suppose \(K\) has \(d\) digits. Then there exists a valid solution that has exactly \(d\) more digits than \(K\). (This is true because there always exists at least one multiple of \(K\) between \(S \dot{+} 00 \dots 0\) and \(S \dot{+} 99 \dots 9\).) Thus, it is sufficient to consider cases where the digit count increases by at most \(d\).

Consider representing a solution as \(t_{upper} \dot{+} S \dot{+} t_{lower}\). Then we may assume that \(|t_{upper}| + |t_{lower}| \leq d\), where \(t_{upper}\) may possible have leading zeros. We consider two cases depending on which of the two parts have more digits.

If \(|t_{upper}| < |t_{lower}|\)

We try all \(t_{upper}\). Since we can obtain \((t_{upper} \dot{+} S \dot{+} 00 \dots 0) \bmod K\), we can also identify \(t_{lower} \bmod K\). If this can be represented as an integer with \(|t_{lower}|\) digits or less, then that is a valid candidate.

If \(|t_{upper}| \geq |t_{lower}|\)

We try all \(t_{lower}\). Since we can obtain \((S \dot{+} t_{lower}) \bmod K\), we can also identify \(t_{upper} \times 10^{|S| + |t_{lower}|} \bmod K\), which we denote by \(x_{upper}\).

Now let \(g\) be the greatest common divisor of \(10^{|S| + |t_{lower}|}\) and \(K\). If \(x_{upper}\) is not a multiple of \(g\), then this case is infeasible. If \(x_{upper}\) is a multiple of \(g\), then we can find the inverse element \(y\) of \(\frac{10^{|S| + |t_{lower}|}}{g}\) modulo \(\frac{K}{g}\), which reveals that \(x_{upper} \times y \bmod K\) is the minimum possible value for \(t_{upper}\).

To find the inverse element \(y\), it is concise to use Euler’s theorem. If \(a \perp k\) and \(ay \bmod k = 1\), then \(y\) can be found as \(a^{\phi(a)-1}\) using the totient function.

Summary of observations

Among the distributions \((0,d), (1,d-1), \dots, (d,0)\) of digits, the feasible candidate that has the lexicographically smallest \((t_{upper}, t_{lower})\) is the solution.

When integers are represented as strings, the ordering as integers coincides with the lexicographical ordering of (number of digits, string representation). Using this fact, we can compare at most \((d + 1)\) candidates to find the final solution.

The computational complexity is \(O((|S|d + d^2) + 10^{d/2} \log(K))\), which is fast enough.

Sample code (C++)

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <array>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::string;
using std::to_string;
using std::pair;
using std::make_pair;
using std::vector;
using std::min;
using std::max;
using std::array;
#include <atcoder/all>

typedef long long int ll;

ll k;
string s;

ll bpow (ll l, ll r, ll m) {
	l %= m;
	ll x = 1;
	while (r) {
		if (r & 1LL) {
			x = (x * l) % m;
		}

		l = (l * l) % m;
		r >>= 1;
	}
	return x;
}
ll binvprime (ll x, ll p) {
	return bpow(x, p-2, p);
}
ll gcdeuc (ll x, ll y) {
	if (y == 0) return x;
	return gcdeuc(y, x % y);
}

string makestrd (ll x, ll d) {
	string s = "";
	vector<char> ss(d);
	for (ll i = 0; i < d; i++) {
		ss[i] = '0' + (x % 10);
		x /= 10;
	}
	for (ll i = 0; i < d; i++) {
		s += ss[d-1-i];
	}
	return s;
}

vector<pair<ll, ll> > factorize (ll x) {
	vector<pair<ll, ll> > plist;
	for (ll i = 2; i * i <= x; i++) {
		if (x % i != 0) continue;

		ll cnt = 0;
		while (x % i == 0) {
			x /= i;
			cnt++;
		}

		plist.push_back({i, cnt});
	}
	if (x > 1) {
		plist.push_back({x, 1});
	}
	return plist;
}
vector<pair<ll, ll> > subf (const vector<pair<ll, ll> > &l, const vector<pair<ll, ll> > &r) {
	vector<pair<ll, ll> > x;
	ll li = 0, ri = 0;
	while (li < l.size()) {
		while (ri < r.size() && r[ri].first < l[li].first) ri++;

		ll lc = l[li].second;
		if (ri < r.size() && r[ri].first == l[li].first) {
			lc -= r[ri].second;
		}
		if (lc > 0) {
			x.push_back({l[li].first, lc});
		}

		li++;
	}
	return x;
}
ll tortient (const vector<pair<ll, ll> > &plist) {
	ll ans = 1;
	for (auto &[p, cnt] : plist) {
		for (ll i = 0; i < cnt; i++) {
			ans *= ((i==0) ? p-1 : p);
		}
	}
	return ans;
}


const ll MAX_D = 9;

void solve () {
	vector<ll> p10(MAX_D + 1);
	p10[0] = 1;
	for (ll i = 1; i <= MAX_D; i++) {
		p10[i] = p10[i-1] * 10;
	}

	ll smodk = 0;
	for (ll i = 0; i < s.size(); i++) {
		smodk = (smodk * 10 + (s[i]-'0')) % k;
	}

	vector<pair<ll, ll> > fk = factorize(k);

	string sans = "";
	ll opti = -1;
	for (ll i = 0; i <= MAX_D; i++) {
		ll j = MAX_D - i;
		// [at most j digits] S [i digits]
		ll h = bpow(10, s.size() + i, k);
		ll base = smodk * bpow(10, i, k);
		// C * h + base + D == 0 (mod k)

		ll g = gcdeuc(h, k);
		vector<pair<ll, ll> > fg = factorize(g);
		vector<pair<ll, ll> > fq = subf(fk, fg);
		ll tort = tortient(fq);
		ll pk = k/g, ph = h/g;

		ll cmin = -1, dmin = -1;
		if (i <= j) {
			// lower part
			for (ll d = 0; d < p10[i]; d++) {
				ll b = base + d;
				if (b % g != 0) continue;

				ll c = (k/g - ((b/g)%(k/g))) * bpow(h/g, tort - 1, k/g) % (k/g);
				if (cmin == -1 || make_pair(c, d) < make_pair(cmin, dmin)) {
					cmin = c;
					dmin = d;
				}
			}
		} else {
			// upper part
			for (ll c = 0; c < p10[j]; c++) {
				ll d = (k - (c * h + base) % k) % k;
				
				if (d >= p10[i]) continue;

				if (cmin == -1) {
					cmin = c;
					dmin = d;
					break;
				}
			}
		}

		if (cmin != -1) {
			string cand = ((cmin == 0) ? "" : to_string(cmin)) + s + makestrd(dmin, i);

			if (sans == "" || make_pair(cand.size(), cand) < make_pair(sans.size(), sans) ) {
				sans = cand;

				opti = i;
			} 
		}
	}
	cout << sans << "\n";
	// cerr << opti << endl;
}

int main (void) {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T;
	cin >> T;
	for (int ti = 0; ti < T; ti++) {
		cin >> k;
		cin >> s;

		solve();
	}

	return 0;
}