G :: Nightmare

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Mosjava stuck at a nightmare. Every night when fall asleep a similar nightmare comes, in that nightmare he first is in Dezfoul then the city changes to Isfahan, the city alternatively change at a period of p. He has too many good and bad memory in both. If he goes to a place with bad memory he will wake up immediately and his day will be ruined. The only way he can wake up with full energy is to go to a specific place that he has the best memory there. 

Given map of Dezfoul and Isfahan with place of bad and the best memory and start, it is guaranteed that there is only one best memory place and starting location always is in Dezfoul. Going from a place to another take 1 unit of time. Each city is a n×n square. 

 

There is an example shown below with period of 3. B is the best memory place, X means bad memory place and S is the starting location. The shortest time to reach to best place is 6. 

Help Mosjava get up as early as possible with full energy. 

Input

In the first line of input there is T, number of test-cases. 

Each test case starts with two integer n (1≤n≤50) and p (1≤p≤50). Then comes 2n+1 lines in follow, each having n character representing the map of cities except n+1th line. The first map belongs to Dezfoul and second is Isfahan. 

‘B’ : Best memory place ‘X’ : Bad memory place ‘S’ : Start location ‘.’ : Ordinary location 

Output

For each test-case, print the earliest possible time Mosjava could wake up with full energy. If there is no way print “NO ANSWER” without quotes. 

Sample Input

1
3 3
BXX
XX.
S..
...
XX.
XXX

Sample Output

6

Submit

Source: 13th Iran Nationwide Internet Contest - Isfahan