题号：NC15536
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Aguin has two strings A with the length of n and B with the length of m only contains lowercase letters.
But the strings are such antiques that some characters can’t be recognized (replaced with ’*’), and it can be any lowercase letters.
Now Aguin is wondering whether A is a substring of B. However, his way of match is a little strange. The detailed rules for match are as follows : the beginning of the A is aligned with the itℎ character of the B, and every character in the A can find the same one in B, and the position deviation does not exceed the k, then it is considered that A is matched with B in the subordinate position of the B. That is to say, for all j(1 ≤ j ≤ |A|), there is a p(1 ≤ P ≤ |B|), which the | j−(p−i+1) |≤k, i+j≤m and A[j] = B[p] all valid. 
But the strings are such antiques that some characters can’t be recognized (replaced with ’*’), and it can be any lowercase letters.
Now Aguin is wondering whether A is a substring of B. However, his way of match is a little strange. The detailed rules for match are as follows : the beginning of the A is aligned with the itℎ character of the B, and every character in the A can find the same one in B, and the position deviation does not exceed the k, then it is considered that A is matched with B in the subordinate position of the B. That is to say, for all j(1 ≤ j ≤ |A|), there is a p(1 ≤ P ≤ |B|), which the | j−(p−i+1) |≤k, i+j≤m and A[j] = B[p] all valid.
And if k=0, string ”***” can be matched with any other strings which length is 3.
Given strings A, B and the number k, you are supposed to find how many locations can A be matched in B.
Given strings A, B and the number k, you are supposed to find how many locations can A be matched in B.
输入描述:
The first line contains an integer number T, the number of test cases.
For each test case :
The first line contains three integers n,m(1 ≤ n ≤ m ≤ 105),k(1 ≤ k ≤ 105), length of A, B and the number of deviation.
The second line contains a string A with the length of n.
The third line contains a string B with the length of m.
It is guaranteed that the strings contains only lowercase letters and ’*’.
输出描述:
For each test case print the number of locations can S be matched in T.