{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}

import Debug.Trace
import Data.Maybe
import qualified Data.IntSet as S
import qualified Data.List as L
import qualified Data.IntMap as M
import qualified Data.ByteString.Char8 as B
import qualified Data.Foldable as F

type Index = Int
type StartPoints = S.IntSet
type Board = (M.IntMap B.ByteString)
type Memo = (M.IntMap (M.IntMap Int))
type Point = (Index, Index)

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]

toI (y, x) = y * 1000 + x
fromI p = (floor(fromIntegral p / 1000), p `mod` 1000)

bfs b k p@(sy, sx) h w = toStartPoints queue
  where
    inner (y, x) = not (y < 0 || y >= h || x < 0 || x >= w)
    walk _ _ 0 _ = []
    walk b visited m ((k', (y, x)) : q) =
      let
        ok p k' = not (S.member (toI p) visited || v b p /= '.' || k' == 0)
        nexts = map (\(dy, dx) -> (y + dy, x + dx)) d
        neighbors = [(k'-1, p) | p <- nexts, inner p, ok p k']
        visited' = L.foldl' (\z (_, p) -> S.insert (toI p) z) visited neighbors
        m' = m + length neighbors - 1
      in
        neighbors ++ walk b visited' m' q
    queue = (k, p) : walk b (S.fromList [toI (sy, sx)]) 1 queue
    toStartPoints q = S.fromList (map (\(_, p) -> toI p) q)


listStart :: Board -> Int -> Int -> Int -> StartPoints
listStart b k = bfs b k s
  where s = find b 'S'

solve :: [B.ByteString] -> Int
solve (xs:xss) = 1 + ceiling (fromIntegral m / fromIntegral k)
  where
    [h, w, k] = map readInt $ B.words xs
    b = M.fromList $ zip [0..] xss
    s = listStart b k h w
    m = S.foldl' (\z p -> let (y,x) = fromI p
                          in min z (minimum [y, x, h-y-1, w-x-1])) 1000000000 s

readInt = fst . fromJust . B.readInt
main = B.getContents >>= print . solve .  B.lines

--------------------------------------------------
-- Matrix
--------------------------------------------------
class (Show a) => Matrix a b | a -> b, b -> a where
   v :: a -> (Int, Int) -> b
   find :: a -> b -> (Int, Int)
   findAll :: a -> b -> [(Int, Int)]
   update :: a -> Int -> Int -> b -> a
   initMat :: Int -> Int -> b -> a

instance Matrix Memo Int where
  v b (i, j) = (b M.! i) M.! j
  update b i j c = M.update (Just . M.update (\x -> Just c) j) i b
  initMat i j c = M.fromList $ zip [0..(i-1)] $ L.replicate i xs
    where xs = M.fromList $ zip [0..(j-1)] $ L.replicate j c
  findAll b c = concatMap (\(y, xs) -> zip [y, y..] xs) $ M.toList $ M.map (map fst . M.toList . M.filter (== c)) b

instance Matrix Board Char where
  v b (i, j) = B.index (b M.! i) j
  find b c = head tmp3
    where
      tmp = M.map (B.elemIndex c) b
      tmp2 = M.filterWithKey (\i x -> isJust x) tmp
      tmp3 = map (\(i, x) -> (i, fromJust x)) (M.toList tmp2)
  update b i j c = M.update (Just . replace) i b
    where
      replace x = B.append (B.take j x) $ B.cons c (B.drop (j+1) x)

pp b d = M.foldl' (\z' xs -> z' ++ M.foldl' (\z y -> z ++ (if y == d then "x" else show y)) "" xs ++ " ") "" b
