入力

入力は以下の形式で標準入力から与えられる。

H W T
s_{1,1}s_{1,2} .. s_{1,W}
s_{2,1}s_{2,2} .. s_{2,W}
:
s_{H,1}s_{H,2} .. s_{H,W}

• 1 行目には、 3 個の整数 H, W, T (2 ≦ H, W ≦ 10, 2 ≦ T ≦ 10^9) が与えられる。これらはそれぞれ、マスの行数と列数、および高橋君の目標時間を表す。
• 2 行目から H + 1 行目には、各マスの情報が与えられる。 i + 1 行目の j 文字目 s_{i,j} が i 行 j 列目のマスに対応する。各文字の意味は以下の通り：
  • . : スタート地点にもゴール地点にも指定されていない白マス
  • S : スタート地点として指定された白マス
  • G : ゴール地点として指定された白マス
  • # : 黒マス
  これら以外の文字は s_{i,j} として出現せず、 S および G はそれぞれちょうど 1 個ずつ出現する。また、入力では求める最大値が存在することが保証される。すなわち、少なくとも 1 度は黒マスに移動しなければスタート地点から出発してゴール地点に到着できないこと、および x = 1 のとき T 秒以内にゴール地点に到着することが可能であることが保証される。

部分点

この問題には部分点が設定されている。

• 40 点分のテストケースは 2 ≦ H, W ≦ 3, 2 ≦ T ≦ 30 を満たす。
• 別の 30 点分のテストケースは 2 ≦ T ≦ 30 を満たす。

（※ 問題 D にも部分点が設定されています。そちらもご確認ください。）

出力

標準出力に、 高橋君が T 秒以内にゴール地点に到着することが可能であるような正整数 x の最大値を出力せよ。

末尾の改行を忘れないこと。