Notice that you need to read the statement of "D. Robots Easy" in order to understand this problem.
Also notice the unusual 5 megabytes memory limit.
Alice now is trying to beat the harder version of this puzzle, the only difference from the easy version is that there are 4 robots instead of 1, when ordering the robots to move in a specific direction, all 4 robots move at the same time(that is you can't order a single robot to move).
If the cell the robot should move to is blocked, then the robot doesn't move, if it's empty or crossed then it does move, if the cell already has another robot standing in it then if that robot in that cell is moving then the current robot will also move, otherwise it will not move.
For example if there's a robot in cell $$$(1,1)$$$ and another in cell $$$(1,2)$$$ and you order the robots to move to the left, then both of these robots won't move, but if there's a robot in cell $$$(1,2)$$$ and another in cell $$$(1,3)$$$ and you order the robots to move to the left then both robots will move to the left.
In order to beat the level you need to move the robots such that in the end each robot is standing in a crossed cell. Alice couldn't solve any of the hard levels, can you solve them with at most 1000 moves for a level?
In the first line you will be given the integer $$$L$$$($$$1 \le L \le 1000$$$), the number of levels you need to solve.
Then you will be given $$$L$$$ lines describing the levels, each line will contain eight integers $$$r_1,c_1,r_2,c_2,r_3,c_3,r_4,c_4$$$($$$1 \le r_i,c_i \le 12,1\le i\le 4$$$), the positions of the robots, it's guaranteed that none of the cells are blocked cells and all four cells are distinct.
The output is the same as the easy version.
1 4 2 4 9 11 2 10 10
2 RU
