Problem of the day
βBβ = 4, βSβ = β4321β, βKβ = 3.
The given number is not stable as βS[3]β is not the same as βS[0]β but 3%3 = 0 same as 0%3. βS[3] = 1β and βS[0] = 4β. But the number β4324β is stable. As, for all βiβ, βS[i]β = βS[i%K]β and β4324β is also greater than the given number. It can be proved that this is the best possible answer.
Hence, the answer is β4324β.
The first line contains a single integer βTβ denoting the number of test cases, then the test case follows.
The first line of each test case contains two single space-separated integers, βBβ and βK'.
The second line contains a string with βBβ characters representing the string βSβ.
For each test case, return the minimum stable number whose value is the same or exceeds the value of βAβ.
Output for each test case will be printed on a separate line.
You are not required to print anything; it has already been taken care of. Just implement the function.
1 β€ T β€ 10
1 β€ B β€ 10^5
1 β€ K β€ 10^9
Itβs guaranteed that sum of βBβ over all cases does not exceed 10^5.
The given number will not contain leading zeros.
Time limit: 1 sec
2
4 2
6825
3 3
420
6868
420
For test case 1:
6868 is the minimum possible, stable number. We can see that it is stable because βS[0] = S[2]β because 0%2 = 2%2, and βS[1] = S[3]β because 1%2 = 3%2. All the conditions are satisfied.
Hence, 6868 is the answer.
For test case 2:
The given number itself is stable, and hence it is the best possible answer.
2
5 1
40369
4 2
8516
44444
8585