Problem: Unknown pathogen

Dr. Hideyo discovered an unknown pathogen. This pathogen has a chain structure in which two types of bacteria called Akdamakin and Zendamakin are linked in a straight line. We want to detoxify this pathogen for humankind.

It is known that this pathogen weakens when the length is 2 or less and is detoxified by immunity. Dr. Hideyo can cut this pathogen anywhere to make two chains, the first half and the second half. You can also connect two chains into one chain.

However, it should be noted that chains with a large number of Akdamakin are extremely harmful. When the number of Akdamakins in a chain exceeds the number of Zendamakins, the Akdamakins begin to grow indefinitely at that moment. This is no exception for chains with a length of 2 or less, so you must carefully cut the chains.

Is it possible to make one chain harmless by making it 2 or less in length without making a chain that has more Akdamakins at any moment? Dr. Hideyo has instructed you, your assistant, to write a program to determine if detoxification is possible. Create a program that outputs the operation if detoxification is possible, and outputs that it is impossible if it is not possible. However, the number of steps for that operation does not have to be minimal.

Input / output example

Input example


6
oooxxxx
ooooxxx
oxxooxxo
ooxx
oo
ooo


Output example


-1
7
split 0 0
join 2 1
split 3 4
split 4 0
join 7 6
split 8 2
split 9 0
3
split 0 1
split 2 1
split 4 1
-1
0
1
split 0 0


For example, the second pathogen ooooxxx in the input example
split 0 0 creates o (1) and oooxxx (2). Here, the numbers in parentheses represent identification numbers.
join 2 1 creates oooxxxo (3) and 1 and 2 disappear.
split 3 4 gives oooxx (4) and xo (5). At this time, there is a chain of {oooxx (4), xo (5)}.
split 40 produces o (6) and ooxx (7). {xo (5), o (6), ooxx (7)}
ooxxo (8) can be created by join 7 6. {xo (5), ooxxo (8)}
split 8 2 produces oox (9) and xo (10). {xo (5), oox (9), xo (10)}
The split 90 results in {xo (5), xo (10), o (11), ox (12)} and ends.



input

The input is given in the following format.


Q
str1
str2
::
strQ


The number of pathogens Q (1 ≤ Q ≤ 300) is given on the first line. The following Q line is given a single string stri consisting of'o'(Zendamakin) and'x' (Akudamakin) representing the initial state of each pathogen. The length of the string stri is 1 or more and 100 or less.

output

For stri, if there is a column of disconnect / join operations that meets the requirements, the first row of output outputs an integer n representing the length of the operation column, and the following n rows contain the operation content 1 per row. Outputs each operation in order from the first operation.

The disconnect operation should be expressed in the following format.


split a p


a is an integer representing the identification number of the chain to be cut, and p is the position to cut the chain. As a result of this operation, chain a is cleaved immediately after the p-th (serial number starting with 0) fungus from the beginning. Of the two new chains, the first half is given the identification number m + 1 and the second half is given the identification number m + 2 (where m represents the highest identification number ever assigned. ). Also, the chain a disappears.

The join operation should be expressed in the following format.


join a b


a and b are integers representing the identification numbers of the chains to be joined. The result of this operation is a new chain with the beginning of chain b joined to the end of chain a. The newly created strand is given the identification number m + 1 (where m represents the highest identification number ever given). Also, the chains a and b disappear.

The first strand given as input is given the identification number 0.

As a result of the operation, if the chain is disassembled to meet the requirements of the problem, any operation is judged to be the correct answer. The length of the operation sequence does not necessarily have to be the shortest. However, the length of the operation sequence must be 20000 or less. Whenever a chain is decomposable in a dataset, it is guaranteed that there is an operating sequence that meets this condition.

If an invalid operation sequence is output, it is judged as an incorrect answer. The illegal operation sequence includes the following cases.

* If 0 ≤ p <(length of chain a) -1 is not satisfied in the split operation split a p.
* When the identification number of the chain to be the target of the cutting / joining operation has not been generated yet, or when it has disappeared because it has already been the target of another operation.
* In the join operation join a b, if a and b are equal.



If there is no disconnect / join operation column that satisfies the request, "-1" is output.

Example

Input

6
oooxxxx
ooooxxx
oxxooxxo
ooxx
oo
ooo


Output

-1
7
split 0 0
join 2 1
split 3 4
split 4 0
join 7 6
split 8 2
split 9 0
3
split 0 1
split 2 1
split 4 1
-1
0
1
split 0 0

Solution (in CPP):

Solution:
#include<iostream>
#include<cstdio>
#include<string>
#include<cassert>
#include<vector>
#include<queue>
using namespace std;
static const int DEAD = -1;
static const int EVEN = 0;
static const int GOOD = 1;
static const int OVER = 2;

int gID;
vector<string> ops;

string itoa(int x){
  char s[20];
  sprintf(s, "%d", x);
  return string(s);
}

class Gen{
public:
  string str;
  int id;
  Gen(string s="", int i=0):str(s), id(i){}

  int getState(){
    assert( str.size() > 0 );
    int o = 0, x = 0;
    for ( int i = 0; i < str.size(); i++ ){
      if ( str[i] == 'o' ) o++;
      else if ( str[i] == 'x' ) x++;
      else assert(false);
    }
    if ( x == 0 ){
      assert( o > 0 );
      return GOOD;
    } else if ( x == o ) return EVEN;
    else if ( o > x ) return OVER;
    else return DEAD;
  }
  int length(){ return (int)str.size(); }

  pair<Gen, Gen> split(int pos){
    assert( 0 <= pos && pos < length()-1);
    ops.push_back("split " + itoa(id) + " " + itoa(pos) );
    Gen l = Gen(str.substr(0, pos+1), gID++);
    Gen r = Gen(str.substr(pos+1), gID++ );
    return make_pair(l, r);
  }

  Gen join(Gen g){
    ops.push_back("join " + itoa(id) + " " + itoa(g.id));
    string s = str + g.str;
    return Gen(s, gID++);
  }

  bool startsWith(string s){
    if ( str.size() < s.size() ) return false;
    return str.substr(0, 2) == s;
  }

  bool endsWith(string s){
    if ( str.size() < s.size() ) return false;
    return str.substr(str.size()-2) == s;
  }

};

typedef pair<Gen, Gen> Gen2;

bool solveEven(Gen g){
  assert( g.length()%2 == 0 && g.length() > 0 );
  for ( int i = 0; i < g.length(); i+=2 ){
    if ( !(g.str.substr(i, 2) == "ox" || g.str.substr(i, 2) == "xo" ) ){
      return false;
    }
  }
  while( g.length() > 2 ){
    Gen2 w = g.split(1);
    g = w.second;
  }
  return true;
}

void solveEvens(queue<Gen> evens, Gen good){
  while( !evens.empty() ){
    Gen even = evens.front(); evens.pop();
    assert( even.getState() == EVEN );
    if ( even.length() <= 2 ) continue;
    Gen tmp;
    
    while( even.length() > 2 ){
      assert( good.str == "o" );
      while( even.length() >= 4 && (even.startsWith("xo") || even.startsWith("ox"))){
	Gen2 w = even.split(1);
	even = w.second;
      }
      while( even.length() >= 4 && (even.endsWith("xo") || even.endsWith("ox"))){
	Gen2 w = even.split(even.length()-3);
	even = w.first;
      }
      if ( even.length() == 2 ) break;

      if ( even.startsWith("oo") && even.endsWith("xx") ){
	tmp = even.join(good);
	Gen2 w = tmp.split(tmp.length()-3);
	Gen2 y = w.first.split(0);
	good = y.first;
	even = y.second;
      } else if ( even.startsWith("xx") && even.endsWith("oo") ){
	tmp = good.join(even);
	Gen2 w = tmp.split(1);
	Gen2 y = w.second.split(w.second.length()-2);
	even = y.first;
	good = y.second;
      } else if ( even.startsWith("oo") && even.endsWith("oo") ){
	tmp = even.join(good);
	Gen2 w = tmp.split(0);
	tmp = w.second.join(w.first);
	Gen2 y = tmp.split(0);
	good = y.first;
	even = y.second;
      } else if ( even.startsWith("xx") && even.endsWith("xx") ){
	int f = 0;
	int c = 0;
	for ( c = 0; ; c++ ){
	  if ( even.str[c]  == 'x' ) f--;
	  else f++;
	  if ( f == 0 ) break;
	}
	Gen2 w = even.split(c);
	assert( w.first.length() >= 2 && w.first.getState() == EVEN );
	assert( w.second.length() >= 2 && w.second.getState() == EVEN );
	evens.push(w.first);
	evens.push(w.second);
	even = Gen("", -1);
      } else {
	cout << even.str << endl;
	assert( false );
      }
    }
  }
}

void solveOver(Gen g){
  queue<Gen> evens;
  Gen good;

  while(1){
    if ( g.getState() == GOOD ){
      good = g;
      break;
    }

    for ( int i = 0, f = 0; i < g.str.size(); i++ ){
      if ( g.str[i] == 'o' ){
	f++;
	if ( f == 0 ) {
	  Gen2 w = g.split(i);
	  evens.push(w.first);
	  g = w.second;
	  f = 0;
	  break;
	}
      } else if ( g.str[i] == 'x' ){
	f--;
	if ( f >= 0 ){
	  while(f--){
	    Gen2 w = g.split(0);
	    assert( w.first.str[0] == 'o');
	    g = w.second.join(w.first);
	    i--;
	  }
	  Gen2 w = g.split(i);
	  evens.push(w.first);
	  g = w.second;
	  break;
	}
      }   
    }
  }
  assert( good.getState() == GOOD );

  while( good.length() > 1 ){
    Gen2 w = good.split(0);
    good = w.second;
  }

  solveEvens(evens, good);
}

void solve(string str){
  gID = 0;
  ops.clear();
  Gen g = Gen(str, gID++);
  if ( g.getState() == DEAD ){
    cout << -1 << endl;
    return;
  } else if ( g.getState() == EVEN ){
    if ( !solveEven(g) ){
      cout << -1 << endl;
      return;
    }
  } else if ( g.getState() == GOOD || g.getState() == OVER ){
    solveOver(g);
  }

  cout << ops.size() << endl;
  for ( int i = 0; i < ops.size(); i++ ) cout << ops[i] << endl;
}

int main(){
  int tcase; cin >> tcase;
  for ( int i = 0; i < tcase; i++ ){
    string g; cin >> g;
    solve(g);
  }
  return 0;
}