Sashank and Neeraj have come to SIES GST for the first time for ByteCamp2019. They have made tiny devices that broadcast their locations(X,Y). While walking around campus they noticed that (N) devices have fell down from their bag. Sashank has a monitor that shows location of all the devices and both of them are facing north. Neeraj has to collect all the devices avoiding walls as soon as possible and return back to Sashank(Xp,Yp). Help Sashank to provide instructions to Neeraj via phone.
Move forward to next place
Turn towards left standing on same place
Turn towards right standing on same place
Turn backward standing on same place
The first line of input contain an integer T denoting the number of test cases.
First line of each test case contains N denoting number of devices.
Next line has space separated integers Xp and Yp .
It is followed by a line containing 2 space separated integers Xmax and Ymax denoting number of horizontal and vertical elements.
Next Y line contain matrix of 1s and 0s. Where 0 is for walls and 1 is for path.
Next N lines have space separated X and Y coordinate of the devices.
For each test case print minimum number of instructions to cover all device in same order as input.
Print “lost” without quotes if collecting all devices is not possible.
T < 101
0 < N < 6
X, Y < 21
No possible path.