AT_abc423_g [ABC423G] Small Multiple 2

Find the minimum possible value of a positive integer $ n $ that satisfies the following two conditions: - $ n $ is a multiple of $ K $ . - The decimal representation of $ n $ contains $ S $ as a substring. $ T $ test cases are given, so find the answer for each. What is a substring? A substring of a string $ S $ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $ S $ . For example, `ab` and `b` are substrings of `abc`, but `ac` and `cba` are not substrings of `abc`.

The input is given from Standard Input in the following format: > $ T $ $ \textrm{case}_1 $ $ \textrm{case}_2 $ $ \vdots $ $ \textrm{case}_T $ $ \textrm{case}_i $ represents the $ i $ -th test case. Each test case is given in the following format: > $ K $ $ S $

Output $ T $ lines. The $ i $ -th line ( $ 1 \leq i \leq T $ ) should contain the answer to the $ i $ -th test case.

### Sample Explanation 1 In the first test case, among positive integers that are multiples of $ 271 $ , the minimum one whose decimal representation contains `414` as a substring is $ 34146 $ . In the second test case, among positive integers that are multiples of $ 15 $ , the minimum one whose decimal representation contains `23` as a substring is $ 1230 $ . In the third test case, among positive integers that are multiples of $ 155521 $ , the minimum one whose decimal representation contains `1000` as a substring is $ 100000003 $ . In the fourth test case, among positive integers that are multiples of $ 920950937 $ , the minimum one whose decimal representation contains `999999999999999999999` as a substring is $ 1000000999999999999999999999 $ . ### Constraints - $ T $ is an integer. - $ 1 \leq T \leq 200 $ - $ K $ is an integer. - $ 1 \leq K \leq 10^9 $ - $ S $ is a string consisting of digits (`0` - `9`). - The first character of $ S $ is not `0`. - $ 1 \leq |S| \leq 5 \times 10^5 $ - For each input file, the sum of $ |S| $ over all test cases is at most $ 5 \times 10^5 $ .