長さ \(N\) の 01 文字列 \(S=S_1S_2\ldots S_N\) が与えられます．
整数 \(1\leq l\leq r\leq N\) に対して，\(S[l,r]\) を文字列 \(S_lS_{l+1}\ldots S_r\) を二進数として解釈した整数とします．先頭に 0 が含まれる場合も，通常の二進数と同様に解釈します．
区間の集合 \(\mathcal{I}\) が次の条件を全て満たすとき，\(\mathcal{I}\) を \(S\) の 三分解（みぶんかい） と呼びます．
各整数 \(1\leq i\leq N\) について，\(c_i\) を \(\mathcal{I}\) に含まれる区間のうち，位置 \(i\) を含むものの個数とします．このとき，三分解 \(\mathcal{I}\) の 幅 を
\(\displaystyle \max_{1\leq i\leq N} c_i\)
と定めます．
さらに，\(S\) の三分解の幅としてあり得る最小値を，\(S\) の 三幅 と呼びます．ただし，\(S\) の三分解が存在しない場合，三幅を \(-1\) と定めます．
\(S\) の三幅を求めてください．
入力は以下の形式で標準入力から与えられます．
| \(T\) | |
| \(\mathrm{case}_1\) | |
| \(\mathrm{case}_2\) | |
| \(\vdots\) | |
| \(\mathrm{case}_T\) |
各テストケース \(\mathrm{case}_i\) は以下の形式です．
| \(N\) | |
| \(S\) |
制約は以下の通りです．
1 つの入力につき \(T\) 個のテストケースが与えられるので，それぞれについて答えてください．各テストケースについて，\(S\) の三幅を 1 行に出力してください．
32113111210
1 2 -1
1 番目のテストケースでは，区間 \([1,2]\) のみからなる集合は三分解です．\(S[1,2]=3\) は 3 の倍数であり，この三分解の幅は 1 です．
2 番目のテストケースでは，区間 \([1,2]\) と区間 \([2,3]\) からなる集合は三分解です．位置 2 は両方の区間に含まれるため，この三分解の幅は 2 です．幅が 1 の三分解は存在しません．
3 番目のテストケースでは，位置 1 を含み，かつ対応する二進数が 3 の倍数となる区間が存在しません．したがって，三分解は存在しません．