Youth Hostel Dorm

The Utrecht Youth Hostel has a giant dorm which usually accommodates all customers easily. With NWERC in town, however, lots of people would like to stay there and all the space available in the dorm should be used as efficiently as possible. You are assigned to provide the dorm layout.

The size of the dorm is given and the layout should consist of a map of that particular size. The map should display one ‘E’, the point of entrance of the dorm, and furthermore ‘B’s and ‘.’s, indicating beds and empty spaces. The entrance should be located somewhere on the boundary of the dorm and every single bed should be reachable by starting at the entrance and walking through empty squares only. You can only walk in vertical and horizontal directions.

The provided layout should contain as many beds as possible.

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

• One line with two integers l and w with 1 ≤ l, w ≤ 8: the size of the dorm.

Per testcase:

• l lines with w characters: the dorm layout. Any layout with the maximum number of beds is correct.