10272_BubbleMaps

Bubble Inc. is developing a new technology for browsing a map at different zoom levels. Their new technology assumes that the region to be mapped is a rectangular plane surface and it divides this surface in rectangular sub-regions, which represent deeper zoom levels.

Bubble Inc. technology represents maps using a structure known as quad-tree. In a quadtree, a rectangular region named x may be divided in half, both horizontally and vertically, resulting in four equal-sized rectangular sub-regions. Those sub-regions are called child regions of x, and are named xp for the top-left, xq for the top-right, xr for the bottom-right and xs for the bottom-left regions, where xc represents the concatenation of string x and character c = 'p', 'q', 'r' or 's'. For example, if the base region to be mapped is called m, the child regions of m are, from top-left in clockwise order: mp, mq, mr and ms, as illustrated below.

Any region can be further subdivided. For example, the region named ms can be further divided into sub-regions msp, msq, msr and mss, as illustrated below.

As another example, the figure below shows the result of subdividing the child sub-regions of the region named msr.

Sub-regions with names of the same length have the same zoom level, since they represent regions of the same size. Sub-regions in the same zoom level that share a common side are said to be neighbors.

Anything that lies outside the base region m is not mapped and, for every zoom level, all sub-regions of m are mapped.

Bubble's map technology provides a way for the user to navigate from a given sub-region to neighboring sub-regions in the directions up, down, left and right. You mission is to help Bubble Inc. in finding the neighboring sub-regions of a given sub-region. That is, given the name of a rectangular sub-region, you must determine the names of its four neighboring sub-regions.

The input contains several test cases. The first line contains one integer N indicating the number of test cases. Each of the following N lines represents a test case, containing the name of a region composed by C characters ( 2 ≤ C ≤ 5000 ), the first always being the letter 'm' and the following being either 'p', 'q', 'r' or 's'.

For each test case in the input your program must produce one line of output, containing the names of the four neighboring regions of the given region in the order of direction up, down, left, right. For the neighbors that are not mapped you should output <none> instead of its name. Leave one blank space between two consecutive names.

2
mrspr
mps

mrspq mrssq mrsps mrsqs
mpp msp <none> mpr