Mr O is teaching Algorithms 101 to his students. The class just finished learning BFS and now he wants to test their understanding. So he came up with the idea of telling them to solve the shortest path problem in a grid. In particular, A grid has rows and columns and Mr O has marked some grid cells as "obstacles". His students have to find the shortest distance from a "start" cell to an "end" cell. From a cell one can go left, right, up or down provided one does not go outside the grid and the cell they go to is not an obstacle. Mr O will assign two distinct non-obstacle cells as start and end.
Quite happy with himself, he realized that now he has to make testing data to test his students. In other words, he needs to come up with some grids with a known shortest distance between the start and end cell (The length of a path through the grid is the number of cells on the path). Being a bit lazy, Mr O has hired you to construct such grids. He will tell you the grid dimensions and the required shortest distance, you just need to construct the grid. Note that the shortest distance means the count of cells in the shortest path, including the start and end cells.
The first line will contain a positive integer , meaning there will be independent testcases.
Then there will be lines, The -th line will contain 3 integers meaning you have to create a grid where the shortest distance between start and end cell is exactly .
The sum of over all testscases
Under these constraints, it is always possible to create a required grid.
For each testcase , output lines. The -th line will have contiguous characters. The -th character on the -th line should be
#
if cell is an obstacle
s
if cell is a start cell
e
if cell is an end cell
.
otherwise
Note your output must have exactly one start cell and one end cell. There are no constraints on the number of obstacles or free cells. The shortest distance between the start and end cell must be exactly . If there are multiple valid solutions, you can output any.
Input | Output |
---|---|
2 4 4 7 3 5 3 | s... .##. .##. ...e .s.e. ..... ..... |