We’re preparing your current view and syncing the latest data.
You are given a string and a number k. The task is to find the longest substring of the given string such that the substring length is divisible by k and if we split this substring into k equal parts, all parts have the same hash value when each character in these parts is decreased by one. Output any such longest substring.
Input consists of the number of test cases and for each test case the string and the integer k are provided. The solution requires efficient hashing and careful implementation to find the substring that meets the criteria.
The first line contains an integer t, the number of test cases. For each test case: A line containing the string s. A line containing the integer k.
For each test case, output the longest substring that satisfies the conditions described above. If multiple such substrings exist, output any one of them.
1 ≤ t ≤ 10 1 ≤ length of s ≤ 10^5 1 ≤ k ≤ length of s
Example 1
Input
1 abcabcabc 3
Output
abcabcabc
Explanation
The entire string 'abcabcabc' can be split into 3 parts: 'abc', 'abc', 'abc'. After decreasing each character by one (e.g., 'b' -> 'a'), all parts have the same hash and therefore satisfy the condition.