Given two strings s and t, find if there is a substring x of s as long as t such that there are at least k matching characters between x and t.

Constraints / Input format :

There are multiple cases. The first line contains an integer denoting the number of cases T. The next 3*T lines contain the test cases, each having the format s in first line, t in the second, and k in the third. Sum of lengths of all s in the test files <= 2000. 0 < k <= |t| <= |s| in all test cases.