skeep 문자열 2

skeep은 팬클럽을 운영했는데, 팬클럽 입구에서 문제를 풀어야 들어갈 수 있었다.

호반우는 문제를 풀었지만, 문제를 푸는 사람이 많아 들어가려면 몇 시간 기다려야 할 것 같았다.

오래 기다리기 싫었던 호반우는 프리패스권을 얻기로 했다.

프리패스권을 얻으려면 다음과 같은 문제를 풀어야 한다.

길이가 $N$인 소문자 알파벳으로 구성된 문자열 $S$가 주어진다.

문자열 $S$의 부분 문자열이란 $S$의 연속된 일부분에 해당하는 문자열을 의미한다.

수행할 수 있는 작업은 다음과 같다.

• 문자열 $S$에서 어떤 자리에 있는 skeep 이라는 부분문자열을 원하는 소문자 알파벳 하나로 바꾼다.

이 작업을 원하는 만큼 수행해서 가능한 작업의 최대 횟수는 얼마일까?

호반우가 프리패스권을 얻어 skeep 팬클럽에 바로 들어가게 도와주자.

첫 번째 줄에 테스트 케이스 수 $T$인 정수로 주어진다. ($1 \le T \le 1\,000$)

각 테스트 케이스의 첫 번째 줄에 문자열의 길이가 $N$인 정수로 주어진다. ($1 \le N \le 2\,000$)

각 테스트 케이스마다 수행 가능한 최대 횟수를 한 줄에 하나씩 출력한다.