AT_abc443_e [ABC443E] Climbing Silver

$ N \times N $ のマス目があります。このマス目の上から $ i $ 行目、左から $ j $ 列目を $ (i,j) $ と呼びます。 マス目の情報は $ N $ 個の文字列 $ S_1,S_2,\dots,S_N $ として与えられ、 $ S_i $ の $ j $ 文字目が `.` のとき $ (i,j) $ は空きマス、 `#` のとき $ (i,j) $ は壁マスです。 はじめ、高橋君は空きマス $ (N,C) $ におり、以下の移動を $ N-1 $ 回繰り返します。 - 現在高橋君が $ (r,c) $ にいるとき、 $ (r-1,c-1),(r-1,c),(r-1,c+1) $ のいずれかを移動先として指定する。但し、マス目中に存在しないマスを移動先として指定することはできない。 - もし移動先 $ (a,b) $ が壁マスである場合、以下のことが起こる。 - 現時点で $ a < i \le N $ を満たす全ての整数について $ (i,b) $ が空きマスであった場合、 $ (a,b) $ にある壁を破壊し、移動する。すなわち、 $ (a,b) $ は空きマスになり、高橋君は $ (a,b) $ に移動する。 - そうでない場合、高橋君は移動に失敗する。この場合、移動が $ N-1 $ 回に満たなくとも直ちに移動の繰り返しを終了する。 - もし移動先 $ (a,b) $ が空きマスである場合、高橋君は $ (a,b) $ に移動する。 以下の条件を満たす長さ $ N $ の文字列 $ R $ を出力してください。 - もし移動中に失敗せず $ (1,i) $ に辿り着ける場合、 $ R $ の $ i $ 文字目は `1` - そうでない場合、 $ R $ の $ i $ 文字目は `0` $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

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

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 この入力には $ 5 $ 個のテストケースが含まれます。 $ 1 $ 番目のテストケースについて、例えば以下のようにして移動中に失敗せず $ (1,3) $ に辿り着くことができます。 - はじめ、高橋君は $ (5,3) $ にいる。 - 空きマス $ (4,2) $ に移動する。 - $ (3,3) $ は壁マスであるが、現時点で $ (4,3),(5,3) $ は共に空きマスであるため、高橋君は $ (3,3) $ にある壁を破壊して $ (3,3) $ に移動する。 - $ (2,3) $ は壁マスであるが、現時点で $ (3,3),(4,3),(5,3) $ は共に空きマスであるため、高橋君は $ (2,3) $ にある壁を破壊して $ (2,3) $ に移動する。 - $ (1,3) $ は壁マスであるが、現時点で $ (2,3),(3,3),(4,3),(5,3) $ は共に空きマスであるため、高橋君は $ (1,3) $ にある壁を破壊して $ (1,3) $ に移動する。 移動中に失敗せず $ (1,1),(1,3),(1,4),(1,5) $ には辿り着くことができるので、 `10111` と出力してください。 ### Constraints - $ T,N,C $ は整数 - $ 1 \le T \le 50000 $ - $ 2 \le N \le 3000 $ - $ 1 \le C \le N $ - $ S_i $ は `.` と `#` からなる長さ $ N $ の文字列 - $ S_N $ の $ C $ 文字目は `.` - ひとつの入力について、 $ N^2 $ の総和は $ 9 \times 10^6 $ を超えない