import Control.Monad
import qualified Data.Array as A
import Data.Char
import Data.List
import Data.Maybe
import qualified Data.Map.Strict as M
import Data.Ord

main :: IO ()
main = readLn >>= main'
    where
        main' n = replicateM n getLine >>= main'' n
        main'' n ss = getLine >> sloop (edit n ss)

        edit n ss
            | all null ss = []
            | otherwise = rec . foldr ff ([], []) $ ss
            where
                ff [] (hs, ts) = (ord 'a' - 1 : hs, [] : ts)
                ff (x : xs) (hs, ts) = (ord x : hs, xs : ts)
                rec (hs, ts) = A.listArray (0, n - 1) hs : edit n ts

sloop :: [A.Array Int Int] -> IO ()
sloop ss = getContents >>= mapM_ (print . solve ss . read' . words) . lines
    where
        read' [k, qs] = (read k - 1, qmap)
            where
                qmap = M.fromList $ zip (ord 'a' - 1 : fmap ord qs) [0..]

solve :: [A.Array Int Int] -> (Int, M.Map Int Int) -> Int
solve ss (k, qs) = solve' 1 ss (A.indices . head $  ss)
    where
        solve' :: Int -> [A.Array Int Int] -> [Int] -> Int
        solve n _ [_] = n
        solve' n (x : xs) idxs
            | length js == 1 = r
            | otherwise = solve' r xs js
            where
                t = fromJust $ lookup k ts
                ts = fmap (\i -> (i, (qs M.!) . (x A.!) $ i)) idxs
                (r, js) = count $ sortOn snd ts
                count = count' n []
                count' m js ((i, y) : ys)
                    | y < t = count' (m + 1) js ys
                    | y == t = count' m (i : js) ys
                    | otherwise = (m, js)
                count' m js _ = (m, js)
        solve' n [] _ = n
