Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
117 - ZOJ Monthly, June 2012 - H
Hash Function

Time Limit: 3 Seconds      Memory Limit: 65536 KB

Hash table is very important in computer science. A hash function is any algorithm or subroutine that maps large data sets of variable length, called keys, to smaller data sets of a fixed length. For example, a person's name, having a variable length, could be hashed to a single integer. The values returned by a hash function are called hash values, hash codes, hash sums, checksums or simply hashes.

Polynomial hash function is a simple kind of hash function as follow: Assume the key is of the form of a Object with multiple components, (x0, x1, x2, ..., xk-1), for example a string, the individual objects characters. Given a positive integer b, we use the polynomial function f defined below as a naive hash function: f(x,b) = x0bk-1 + x1bk-2 + ... + xk-2b + xk-1 . Because the value of f(x,b) is too large, we usually take the remainder of it divided by a particular prime integer P larger than b.

Here comes the problem, given a string S, a hash function f and integer N, calculate how many substrings(non-empty consecutive characters) of S whose hash value is N.

Input

There are multiple test cases. The first line of input is an integer T(T ≈ 100) indicates the number of test cases. Then T test cases follow. Each test case contains 2 lines. The first line of each test case is a line containing a string S. The second line is an integer b , a prime integer P and another integer N separated by a space. The length of the string S is no longer than 10000 and all the characters are printable whose ASCII value is between 32 and 126 inclusive, 0 <=b,N <P <231.

Output

Output the answer in a single line.

Sample Input

2
BBB
1 2 1
BBB
1 2 0

Sample Output

0
6

Hint

In both of the 2 samples, the hash value of all the substrings are even because the ASCII value of B is 66. There is 1 substring BBB whose hash value is 198. There are 2 substrings BB whose hash value are 132. There are 3 substrings B whose hash value are 66.


Author: CAO, Peng
Submit    Status