AT_abc423_g [ABC423G] Small Multiple 2

以下の $ 2 $ つの条件を満たす正の整数 $ n $ としてあり得る最小値を求めてください。 - $ n $ は $ K $ の倍数である。 - $ n $ の十進法での表記には、部分文字列として $ S $ が含まれる。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。 部分文字列とは ある文字列 $ S $ の部分文字列とは、 $ S $ の先頭から $ 0 $ 文字以上、末尾から $ 0 $ 文字以上削除して得られる文字列のことをいいます。 例えば、`ab` や `b` は `abc` の部分文字列ですが、`ac` や `cba` は `abc` の部分文字列ではありません。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \textrm{case}_1 $ $ \textrm{case}_2 $ $ \vdots $ $ \textrm{case}_T $ $ \textrm{case}_i $ は $ i $ 番目のテストケースを表す。各テストケースは以下の形式で与えられる。 > $ K $ $ S $

$ T $ 行出力せよ。 $ i $ 行目 ( $ 1 \leq i \leq T $ ) には $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースにおいて、 $ 271 $ の倍数である正の整数のうち、十進法での表記に部分文字列として `414` を含むものの最小値は $ 34146 $ です。 $ 2 $ 番目のテストケースにおいて、 $ 15 $ の倍数である正の整数のうち、十進法での表記に部分文字列として `23` を含むものの最小値は $ 1230 $ です。 $ 3 $ 番目のテストケースにおいて、 $ 155521 $ の倍数である正の整数のうち、十進法での表記に部分文字列として `1000` を含むものの最小値は $ 100000003 $ です。 $ 4 $ 番目のテストケースにおいて、 $ 920950937 $ の倍数である正の整数のうち、十進法での表記に部分文字列として `999999999999999999999` を含むものの最小値は $ 1000000999999999999999999999 $ です。 ### Constraints - $ T $ は整数。 - $ 1 \leq T \leq 200 $ - $ K $ は整数。 - $ 1 \leq K \leq 10^9 $ - $ S $ は数字 (`0` - `9`) からなる文字列。 - $ S $ の先頭の文字は `0` でない。 - $ 1 \leq |S| \leq 5 \times 10^5 $ - すべてのテストケースの $ |S| $ の総和は $ 5 \times 10^5 $ 以下である。