#P16830. [NWRRC 2022]Hidden Digits

[NWRRC 2022]Hidden Digits

题目描述

给定一个长度为 nn 的数字序列

d0,d1,…,dn−1.d_0,d_1,\ldots,d_{n-1}.

求最小的正整数 xx,使得对于所有 0≤i<n0\le i<n,整数 x+ix+i 的十进制表示中都至少出现一次数字 did_i。

输入格式

输入包含多组测试数据。

第一行包含整数 tt,表示测试数据组数。

对于每组测试数据:

  • 第一行包含整数 nn;
  • 第二行包含一个长度为 nn 的数字串 d0d1…dn−1d_0d_1\ldots d_{n-1}。

数据范围

1≤t≤105,1\le t\le 10^5, 1≤n≤106,1\le n\le 10^6, 0≤di≤9.0\le d_i\le 9.

所有测试数据的 nn 之和不超过 10610^6。

输出格式

对于每组测试数据,输出一行一个整数 xx,表示满足条件的最小正整数。

样例

6
5
12345
5
01234
3
239
9
998244353
10
1000000007
20
18446744073709551616
1
10
92
45296
701
10367486