You are given two binary strings (where each character is either \(0\) or \(1\)) \(S\) and \(T\), each of length \(N\) and an integer \(X\). You can apply the following two types of operations to the string \(S\):

Choose two distinct indices \(i,j\) and flip both \(S_i, S_j\). The cost of this operation is \(X\).
Choose an index \(i \;(1 \le i \lt N)\) and flip both \(S_i, S_{i+1}\). The cost of this operation is \(1\).

You may perform this operation any number of times. Find the minimum cost to make the strings \(S\) and \(T\) equal or report that it is impossible.

Input format

The first line of input contains an integer \(T\) denoting the number of test cases. The description of each test case is as follows:
The first line of each test case contains two integers \(N\) denoting the length of the string \(S\) and \(T\) and integer \(X\).
The second line of each test case contains the string \(S\).
The third line of each test case contains the string \(T\).

Output format

For each test case, print \(-1\) if it is impossible to equalize the strings. Otherwise print the minimum cost to make the strings \(S\) and \(T\) equal in a separate line.

Constraints

\(1\le T \le 100 \\ 1 \leq N, X \le 2000\\ \text{S and T are binary strings.}\\ \text{Sum of $N$ over all test cases does not exceed }2000.\)