1254: String

There is a string of length n, S[l..r] represents the string concatenated from the lth character to the rth character, and S_len is the length of the string(S[1..S_len] represents the whole S string). We define F_G as the number of positive integers x that satisfy the following conditions: 
1. 1 ≤ x ≤ Glen 
2. G[1, x] = G[Glen − x + 1, Glen] 
3. The length of the common part of the intervals [1, x] and [Glen − x + 1, G_len] is greater than 0 and is divisible by k. 

The first line of input is a positive integer T(T ≤ 10) representing the number of data cases. 
For each cases: 
first line input a string S of lowercase letters, no longer than 10⁶ . 
second line input a positive integer k(1 ≤ k ≤ S_len).

For each cases, output a line with a positive integer representing the answer.

1
abababac
2

24

Note that the stack space of the judge system is a bit small, please pay attention to the reasonable allocation of memory