Accordion

This problem was suggested in the forum by pearl_barley - thanks for the idea!

It is a card game for single player, one of many so-called "Solitaires". The rules are simple:

• cards are shuffled and put out in a single line, faces up
• at every move some card is chosen and put onto its neighbor to the left, or over two neighbors on the third (also to the left) - provided that either rank or suit of the two cards (covering and covered) match
• the cards which were covered are discarded, the line is contracted whenever convenient (we do not regard "gaps" anyway)

The goal is to reduce the line to single card.

Regard the example in the picture above H8 D6 H4 D2 SA H3 D8 - supposing the game is almost over and the deck has been shortened to those 7 cards. Let's call longer move (over two) to the left a "jump" while simple moving onto the closest left neighbor a "shift".

Possible moves are "jumping" D8 over two neighbors onto D2 (their suits match), or "jumping" H3 onto H4 in the same manner. If we first "jump" D8 and on the next move "jump" it further onto H8 (now ranks match), we provide opportunity to "shift" D6 onto D8 on the third move. Anyway this is hopeless game as there is no opportunity to match SA with anything else.

Problem

You are given several "cases" to play, presented by the decks of increasing size.

Solution for each case is the sequence of integers, telling which cards to move, in order. Indices are zero-based, but card with index 0 is not expected to play of course (it could be covered, but can't cover anything as it has no neighbors to the left). For moves which describe "jumps" rather than "shifts" append symbol j to the integer.

Solution for the case of N cards uses N-1 values, of course. However if you would like to skip certain case put a single value 0 instead of the whole solution for it.

All values in each of solutions - and all solutions themselves are simply space-separated (as we know the amount of values in every solution anyway).

Extra Ranks and Suit

To provide greater diversity some cases include 5th rank denoted with letter X (Xyris?) and 3 extra ranks F, M, P (Fool, Magician, Priest). It should be of no much importance for solving algorithm.

Challenge

It is not a real "challenge", but since the "good" solution is not known to me at the moment of creating the problem, the task is "styled" as challenge: you are to solve at least 5 of the cases presented - and the results table shall keep count who solved how many.

Input shall have a count of testcases to follow in the first line.
Next lines contain one testcase each. Testcase is prepended by the integer giving the total number of cards in it.

Answer is a long sequence of all solutions in order, as described above.

Example

input:
3
4 S3 D2 D3 S2
4 S3 D2 S2 D3
6 S3 D2 D3 S2 S4 D4

answer:
3j 1 1 0 5j 4 3j 2 1

Here for the 1st case we jump S2 onto S3 then shift D2 on it and at last shift D3. We skip then the second case simply putting 0. The last case starts with jumping D4 onto D3, shifting S4 onto S2 and then jumping it onto S3. D4 is then shifted twice.