AT_bogosortcontest_div2_d Circulating Ball

円周上に $ N $ 個の箱が並んでおり、時計回りに順に箱 $ 1, 2, \ldots, N $ と番号が付けられています。 各箱には高々 $ 1 $ 個のボールが入っています。 最初の状態は `0`, `1` からなる長さ $ N $ の文字列 $ S $ で与えられ、 $ S_i= $ `1` のとき箱 $ i $ には $ 1 $ 個のボールが入っており、 $ S_i= $ `0` のとき箱 $ i $ にはボールが入っていません。 何個でもボールが入る台車を用いて、以下の操作を考えます。 - 箱を $ 1 $ つ選び、その箱の位置に空の台車を置く。その後、以下の手順を繰り返す。 - 台車の位置にある箱の中のボールの有無と台車の中のボールの有無に応じて、以下のいずれかの処理を行う。 - 箱にボールが入っているとき：箱からボールを $ 1 $ つ取り出して台車に入れる。 - 箱が空であり、かつ台車にボールが入っているとき：台車からボールを $ 1 $ つ取り出して箱に入れる。 - 箱も台車も空のとき：何もしない。 - 上記の処理の後、台車にボールが入っていれば、時計回りに次の箱の位置まで台車を進める。台車にボールが入っていなければ、操作を終了する。 各 $ k = 1, 2, \ldots, N $ について、それぞれ独立に以下の問題を解いてください。 - 初期状態から始めて箱 $ k $ の位置に台車を置いたとき、台車が最終的に停止した位置にある箱の番号を求めよ。 なお、この操作において台車が必ず停止することは証明できます。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ S $

答えを合計 $ T $ 行で出力せよ。 $ t $ 行目には、 $ t $ 番目のテストケースにおける $ k = 1, 2, \ldots, N $ に対する答えを順に空白区切りで出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて説明します。 $ k=1 $ の場合、以下のように操作が進みます。 - 箱 $ 1 $ からボールを回収し、台車のボールが $ 1 $ 個になる。台車は空でないので箱 $ 2 $ に進む。 - 空の箱 $ 2 $ へボールを $ 1 $ つ入れ、台車のボールが $ 0 $ 個になる。台車が空になるため、箱 $ 2 $ で停止する。 $ k=2 $ の場合、以下のように操作が進みます。 - 箱 $ 2 $ も台車も空のため何も起こらず、そのまま箱 $ 2 $ で停止する。 $ k=3 $ の場合、以下のように操作が進みます。 - 箱 $ 3 $ からボールを回収し、台車のボールが $ 1 $ 個になる。台車は空でないので箱 $ 1 $ に進む。 - 箱 $ 1 $ からボールを回収し、台車のボールが $ 2 $ 個になる。台車は空でないので箱 $ 2 $ に進む。 - 空の箱 $ 2 $ へボールを $ 1 $ つ入れ、台車のボールが $ 1 $ 個になる。台車は空でないので箱 $ 3 $ に進む。 - 空の箱 $ 3 $ （最初のステップでボールを回収したため空になっている）へボールを $ 1 $ つ入れ、台車のボールが $ 0 $ 個になる。台車が空になるため、箱 $ 3 $ で停止する。 $ 2 $ つ目のテストケースについて、すべての箱が初期状態で空です。 よって、どの箱 $ k $ から開始しても、箱も台車も空のため何も起こらず、そのまま箱 $ k $ で停止します。 ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 2 \leq N \leq 2 \times 10^5 $ - $ S $ は `0`, `1` からなる長さ $ N $ の文字列 - すべてのテストケースについての $ N $ の総和は $ 2 \times 10^5 $ 以下 - 入力される数値はすべて整数