Andrew and the Strings

Andrew likes strings very much.
He has two strings A and B of N lower alphabet letters. We denote S[i, j] as the substring from i^{th} to j^{th} characters of string S.
Andrew is interested in the number of such fours of integers (L_{A}, R_{A}, L_{B}, R_{B}), where 1 ≤ L_{A} ≤ R_{A} ≤ N, 1 ≤ L_{B} ≤ R_{B} ≤ N, and R_{A} − L_{A} = R_{B} − L_{B}, such that the Hamming distance between substrings A[L_{A}, R_{A}] and B[L_{B}, R_{B}] is not greater than K. Here the Hamming distance between two strings of the same length is the number of unequal characters on the same positions of strings.
Help him and find this number.
Input
The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two spaceseparated integers N and K. The second line contains string A, and the third line contains string B.
Output
For each test case, output an integer, denoting the number of fours (L_{A}, R_{A}, L_{B}, R_{B}) satisfying the conditions described in the problem statements.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 1000
 1 ≤ K ≤ N
 Both A and B are contain only N lower alphabet letters
Example
Input: 3 3 2 aba abb 3 2 abc def 1 1 a a Output: 14 13 1
Explanation
Example case 1: There are 14 fours as following:
(1, 1, 1, 1) : dist(A[1, 1], B[1, 1]) = dist(a, a) = 0 ≤ 2
(1, 1, 2, 2) : dist(A[1, 1], B[2, 2]) = dist(a, b) = 1 ≤ 2
(1, 1, 3, 3) : dist(A[1, 1], B[3, 3]) = dist(a, b) = 1 ≤ 2
(2, 2, 1, 1) : dist(A[2, 2], B[1, 1]) = dist(b, a) = 1 ≤ 2
(2, 2, 2, 2) : dist(A[2, 2], B[2, 2]) = dist(b, b) = 0 ≤ 2
(2, 2, 3, 3) : dist(A[2, 2], B[3, 3]) = dist(b, b) = 0 ≤ 2
(3, 3, 1, 1) : dist(A[3, 3], B[1, 1]) = dist(a, a) = 0 ≤ 2
(3, 3, 2, 2) : dist(A[3, 3], B[2, 2]) = dist(a, b) = 1 ≤ 2
(3, 3, 3, 3) : dist(A[3, 3], B[3, 3]) = dist(a, b) = 1 ≤ 2
(1, 2, 1, 2) : dist(A[1, 2], B[1, 2]) = dist(ab, ab) = 0 ≤ 2
(1, 2, 2, 3) : dist(A[1, 2], B[2, 3]) = dist(ab, bb) = 1 ≤ 2
(2, 3, 1, 2) : dist(A[2, 3], B[1, 2]) = dist(ba, ab) = 2 ≤ 2
(2, 3, 2, 3) : dist(A[2, 3], B[2, 3]) = dist(ba, bb) = 1 ≤ 2
(1, 3, 1, 3) : dist(A[1, 3], B[1, 3]) = dist(aba, abb) = 1 ≤ 2
Example case 2: The four (1, 3, 1, 3) no longer satisfies the conditions, because
(1, 3, 1, 3) : dist(A[1, 3], B[1, 3]) = dist(abc, def) = 3 > 2
Author:  witua 
Tags  cook33, easy, slidingwindow, strings, witua 
Date Added:  28032013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions