There is a faceoff between Spiderman and Sandman.

There are two glass buildings each of height H. Each building has H equal sized windows on the outside covering entire space from bottom to top. Some windows are open and Spiderman cannot land on these window.

In one step, Spiderman can:

1. Rise up to just above window of the same building he is on.
2. Slide down to just below window of the same building he is on.
3. Use his web to jump to Kth window above from current height on the other building.

Sandman on the other rises steadily a rate of 1 per step.

For the purpose of this problem, assume Spiderman and Sandman take turns i.e. Spiderman takes one step, then Sandman takes one step.

Your goal is to assist Spiderman to always remain above or at same height as Sandman at the end of Sandman's turn. Spiderman gets the first turn and both start at height 0 (i.e. Sandman is on the ground and Spiderman is on the window of lowermost floor of left building. It is guaranteed that window of lowermost floor of left building is not open.

Note: If Spiderman gets to area with height ≥ H assume he has got out.

You are Spiderman's best friend, your duty is to guide Spiderman to escape from Sandman if possible in shortest number of steps to get out.

Input

First line contains integer T.

T test cases follow. Each test case contains 3 lines.

First line of input contains two space separated integers H and K

Next two lines contain description of two buildings.

2nd line represents the left building - a string of length H. The i^th character represents the state of window between (i-1) and i heights: character '-' represents closed window (safe to land on), character 'X' represents open window.

Similarly 3rd line represents the right building.

Output

For every test case output single integer x where x is the number of steps taken to get out of building. Output "NO" if Spiderman cannot escape the area and has to fight in the enclosure.

Constraints

1 ≤ T ≤ 10

1 ≤ H, K ≤ 10⁵

Example

Input:
2
7 3
---X--X
-X--XX-
6 2
--X-X-
X--XX-

Output:
4
NO

Explanation

In first case Spiderman jumps to right building, goes one height down, jumps to left building and jumps to right building (he got to the top).

In second case, no matter how he moves, Spiderman cannot escape above the buildings.