DCC intensive Care Contest (Replay)

One upon a time there was a king name Basanta Roy.  He is very famous for his romanticism.  He can do any thing for his queen. One day Enemy trap his queen. Now he tries to rescue his Queen Adrika. But there are too many obstacle in his paths. Dot (.) represents safe yards & Hash (#) represents risky yards which contains bomb. He can move 4 ways left, right, up & down. He can only move one safe yard to another safe yard & it costs 1 energy per move. Can he rescue Adrika? If he can then he should rescue her with minimum amount of energy loss.

Input

Input starts with an integer t≤50 which represents number of test cases. For each case input a pairs of integer R≤100 & C≤100 which represents row & column. Then input R lines containing C number of characters in each. These lines contains only ( . , #, A, B) characters where A and B represents the current positions of  Adrika & Basanta Roy respectively.

Output

For each case print the case number & then print these mentioned below:

If he rescued her then print “I did it! Lost only n energy.”  without quote. N is the lost of energy to recuse the queen Adrika. If he cannot then print “I lost her forever” without quote. For clarification see sample I/Os.

Sample: