You are given two strings a and b consisting of lowercase English letters. A beautiful substring is defined as a substring of any length of string b such that the first and last letters of it are the same as the first and last letters of any substring of length k of string a.

Your task is to count the number of beautiful substrings. Can you?
Input

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains three integers n, m, and k (1 ≤ n, m ≤ 10^5, 1 ≤ k ≤ n), in which n is the length of string a, m is the length of string b, and k is the described variable in the statement.

Then two lines follow, the first line contains a string a of length n and the second line contains a string b of length m. Both strings consist only of lowercase English letters.
Output

For each test case, print a single line containing the number of beautiful substrings
Example
Input

2
4 5 3
acbd
abcbd
3 3 1
kkd
dkd

Output

3
4

Note

A substring of a string s is a sequence sl, sl + 1, …, sr for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), in which n is the length of the string s.

给你两个由小写字母组成的字符串a和b。美丽的子串被定义为字符串b的任何长度的子串，使得它的第一个和最后一个字母与字符串a的长度为k的某子串的第一个和最后一个字母相同。
您的任务是计算漂亮的子字符串的数量。

要<mark>预处理</mark>，不然超时，get到了

#include<cstdio>
#include<cstring>
#include<iostream>
#include <map>
using namespace std;
const int maxn=1e5+5;
char a[maxn],b[maxn];
map<char,int> mp;
int xy[30][30];
int vis[30][30];
int main(){
	int T,n,m,k;
	scanf("%d",&T);
	while(T--){
        mp.clear();
        map<char,int> ::iterator it;
        memset(xy,0,sizeof(xy));
		scanf("%d%d%d",&n,&m,&k);
		scanf("%s",a);
		scanf("%s",b);
		for(int i=m-1;i>=0;i--)
        {
            mp[b[i]]++;
            for(it=mp.begin();it!=mp.end();++it)
            {
                xy[b[i]-'a'][(it->first)-'a']+=it->second;
            }
        }
		char x,y;
		long long ans=0;
		memset(vis,0,sizeof(vis));
		for(int i=0;i+k-1<n;i++)
        {
            x=a[i],y=a[i+k-1];
            if(vis[x-'a'][y-'a'])
                continue;
            else
            {
                ans+=xy[x-'a'][y-'a'];
                vis[x-'a'][y-'a']=1;
            }
        }    		
		printf("%I64d\n",ans);
	}
	return 0;
}