考察

以下では，文字列連結の演算子を \(\dot{+}\) と表記します．

\(K\) は \(d\) 桁であるとします．このとき，桁数が \(d\) だけ増える valid な解が存在します(\(S \dot{+} 00 \dots 0\) 以上 \(S \dot{+} 99 \dots 9\) 以下の整数のうちに必ず \(K\) の倍数が存在することからいえます)．よって，高々 \(d\) 桁増える解のみを考えれば十分です．

\(t_{upper} \dot{+} S \dot{+} t_{lower}\) の形の解を考えます．このとき，\(t_{upper}\) に leading-zero を許したうえで，\(|t_{upper}| + |t_{lower}| \leq d\) としてよいです．桁数の分配それぞれについて，以下の \(2\) 通りに場合分けして解きます．

\(|t_{upper}| < |t_{lower}|\) の場合

\(t_{upper}\) をすべて試します．このとき，\((t_{upper} \dot{+} S \dot{+} 00 \dots 0) \bmod K\) の値が分かることから，\(t_{lower} \bmod K\) の値も分かります．これが \(|t_{lower}|\) 桁以下で表せる値にならば valid な解です．

\(|t_{upper}| \geq |t_{lower}|\) の場合

\(t_{lower}\) をすべて試します．このとき，\((S \dot{+} t_{lower}) \bmod K\) の値が分かることから，\(t_{upper} \times 10^{|S| + |t_{lower}|} \bmod K\) の値 \(x_{upper}\) も分かります．

このとき，\(10^{|S| + |t_{lower}|}\) と \(K\) との最大公約数を \(g\) とし，\(x_{upper}\) が \(g\) の倍数でなければ invalid です．\(x_{upper}\) が \(g\) の倍数であれば，\({}\bmod \frac{K}{g}\) における \(\frac{10^{|S| + |t_{lower}|}}{g}\) の逆元 \(y\) を求めることで，\(x_{upper} \times y \bmod K\) が \(t_{upper}\) としてありうる最小値とわかります．

逆元 \(y\) を求めるには，オイラーの定理によって求めるのが簡潔です．\(a \perp k\)，\(ay \bmod k = 1\) のとき，\(y\) はトーシェント関数を用いて \(a^{\phi(a)-1}\) によって求まります．

考察まとめ

それぞれの桁数の分配 \((0,d), (1,d-1), \dots, (d,0)\) について，valid な 解のうち \((t_{upper}, t_{lower})\) が辞書順最小のものが解候補になります．

文字列表記された整数について，整数としての小ささと (桁数, 文字列表記) の辞書順での小ささは等価です．これを用いて，高々 \(d+1\) 通りの解候補を比較することで，最終的な解が得られます．

計算量は \(O((|S|d + d^2) + 10^{d/2} \log(K))\) となり，十分高速です．

実装例 (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;
}