H. Beautiful Substrings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 ≤ 105, 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.