AT_scpc2026_div2_j DETOX

#### 表示言語 / / $ 1 $ 番から $ N $ 番までの $ N $ 人の生徒が、番号順に円形に座っている。各生徒は、`O`または`X`と書かれた名札を付けている。各生徒は、**自分の名札を除く** $ N-1 $ 人の生徒の名札を見ることができる。同じ文字が書かれた名札をつけた生徒が3人以上連続して座っていることはなく、すべての生徒はこの事実を知っている。 すべての生徒が自分の名札に書かれた文字を当てるまでゲームを進める。ゲームのルールは以下の通りである。 - 各ラウンドごとに、自分の名札に書かれた文字に確信が持てる生徒全員が同時に手を上げる。 - 今回のラウンドでどの生徒が挙手したかを全員が確認した後次のラウンドを始める。 ゲームの進行中、すべての生徒は名札を互いに交換したり、名札を外したり、名札に書かれた文字を変更したりすることはできない。 $ T $ 個のテストケースが与えられる。各テストケースにおいて、各生徒が何番目のラウンドで初めて手を上げるかを求めよ。

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ S $

$ N $ 個の非負の整数をスペースで区切り、テストケースごとに1行に出力する。そのうち $ i $ 番目の整数 $ r_i $ は、 $ i $ 番目の生徒が $ r_i $ 番目のラウンドで初めて挙手することを意味する。もしゲームをいつまでも続けても挙手できない生徒がいるなら、代わりに `-1` を出力する。

### Sample Explanation 1 最初のテストケースでは、4人の生徒がそれぞれ`X`、`O`、`X`、`O`と書かれた名札をつけて円になって座っている。 第1ラウンドで、 $ 2 $ 番の生徒は $ 1 $ 番の生徒と $ 3 $ 番の生徒がともに`X`と書かれた名札をつけていることを確認する。このとき、 $ 2 $ 番の学生が`X`と書かれた名札をつけているとすると、 $ 2 $ 番、 $ 3 $ 番、 $ 4 $ 番の学生が全員`X`と書かれた名札をつけていることになり、隣り合って座っている3人の学生が同じ文字が書かれた名札をつけていないという情報と矛盾する。 したがって、 $ 2 $ 番の生徒は自分が`X`と書かれた名札をつけていることはあり得ず、したがって`O`と書かれた名札をつけていると確信できるため、第1ラウンドで挙手する。他の生徒たちも同様の根拠から、全員第1ラウンドで挙手する。 ### Constraints - $ 1 \le T \le 100\,000 $ - $ 3 \le N \le 100\,000 $ - $ S $ は`O`と`X`のみで構成される長さ $ N $ の文字列である - $ S $ の $ i $ 番目の文字は、 $ i $ 番目の生徒の名札に書かれた文字である - どの並んで座っている3人の学生も同じ文字が書かれた名札をつけていない - すべてのテストケースで与えられる $ N $ の合計は $ 300\,000 $ を超えない - 入力される数値はすべて整数