Count Distinct Rotations

You are given a string S and an integer m. Your task is to count the number of distinct rotations of S that can be generated using at most m rotations. A rotation is defined as taking a prefix of the string and moving it to the end. More formally, if the length of S is \(n\), then a rotation by \(i\) positions transforms S into \(S[i:] + S[:i]\), where \(0 \le i \le \min(n-1, m)\) (note that the 0th rotation is the original string).

For example, when S = "abcdef" and m = 3, the rotations are:

• i = 0: "abcdef"
• i = 1: "bcdefa"
• i = 2: "cdefab"
• i = 3: "defabc"

Thus, there are 4 distinct rotations. Note that if \(m \ge n-1\), you would only generate \(n\) possible rotations.

inputFormat

The input is given via standard input in the following format:

T
S1 m1
S2 m2
... 
ST mT

Where T (1 ≤ T ≤ 1000) is the number of test cases. Each of the following T lines contains a non-empty string S (consisting of lowercase letters) and an integer m (0 ≤ m ≤ 10⁹), separated by space.

outputFormat

For each test case, output a single integer — the number of distinct rotations of the string that can be generated using at most m rotations. Each answer should be printed on a separate line to standard output.

## sample

2
abcdef 3
aaaaaa 5

4
1

</p>