Bubble Maps

Bubble Inc. is developing a new technology for viewing a map at different zoom levels. The region to be mapped is a rectangular plane, and it is recursively divided into rectangular sub-regions that represent deeper zoom levels.

Maps are represented with a structure called a quadtree. A rectangular region named x can be split in half both horizontally and vertically, producing four equal-sized sub-regions. These are the child regions of x:

• xp — top-left
• xq — top-right
• xr — bottom-right
• xs — bottom-left

Here xc denotes the concatenation of the string x and one of the characters p, q, r, s. Listed clockwise starting from the top-left, the children are xp, xq, xr, xs:

+----+----+
| p  | q  |
+----+----+
| s  | r  |
+----+----+

The base region is named m, so its children are mp, mq, mr, ms. Any region can be subdivided further; for example, ms splits into msp, msq, msr, mss.

Two region names of the same length describe regions of the same size and therefore lie at the same zoom level. Two regions at the same zoom level are neighbors if they share a full side. Anything outside the base region m is not mapped, and at every zoom level all sub-regions of m are mapped.

Given the name of a region, determine the names of its four neighboring regions in the directions up, down, left, and right.

The first line contains an integer N, the number of test cases. Each of the following N lines contains one region name made of C characters ($2 \le C \le 5000$): the first character is always m, and each of the remaining characters is one of p, q, r, or s.

For each test case, print one line with the names of the four neighboring regions in the order up, down, left, right, separated by single spaces. If a neighbor lies outside the map, print <none> in place of its name.