Kearan has recently been studying the properties of polynomials with coefficients modulo 2. She discovered that one can obtain a very long string using polynomial multiplication modulo 2:

For a polynomial $f(x)$ of degree $n$ with coefficients 0 or 1, we calculate $g(x) = f(x)^m$ modulo 2. Then $g(x)$ is a polynomial of degree $nm$, which has $nm + 1$ coefficients. By writing these coefficients down from the highest degree to the lowest, we can obtain a 01-string of length $nm + 1$.

For example, for the polynomial $f(x) = x^3 + x + 1$, calculating $g(x) = f(x)^3 = x^9 + x^7 + x^6 + x^5 + x^2 + x + 1$ gives us a string of length 10: 1011100111.

Now, Kearan has a polynomial $f(x)$ of degree $n$, integers $m, L, R$, and a 01-string $t$ of length $K$. Let $s$ be the string obtained from $f(x)^m$, and $s[L, R]$ be the substring of $s$ from the $L$-th character to the $R$-th character. Kearan wants to know how many times $t$ appears in $s[L, R]$.

Input

The first line contains an integer $T$, representing the number of test cases.

For each test case, the first line contains five integers $n, m, K, L, R$.

The second line contains a 01-string of length $n + 1$ representing the coefficients of the polynomial $f(x)$, where the $i$-th character represents the coefficient of the $x^{n-i+1}$ term of $f(x)$.

The third line contains a string of length $K$ representing the string $t$.

Output

For each test case, output a single integer representing the answer.

Constraints

For 100% of the data, it is guaranteed that $1 \le T \le 5$ and $1 \le L \le R \le nm + 1$.

Examples

Input 1

1
3 3 2 1 10
1011
01

Output 1

2