Kick Start

Ksenia는 독서를 무척 좋아해서, 아침 일과를 시작하기 전에 좋아하는 책에서 한 조각을 읽으며 하루를 연다. 조각이란 텍스트의 부분 문자열을 말한다. Ksenia는 다소 미신을 믿어서, 읽은 조각이 문자열 KICK으로 시작하고 그 뒤에 0개 이상의 문자가 이어지다가 문자열 START로 끝나면 그날 하루가 운이 좋다고 믿는다. 조각 전체의 내용이 말이 안 되어도 상관없다.

책의 텍스트가 주어질 때, 책이 낡아서 새로 사야 하기 전까지 Ksenia가 읽을 수 있는 서로 다른 행운의 조각의 개수를 세어라. 두 조각이 텍스트에서 시작 위치나 끝 위치가 다르면, 읽었을 때 같은 내용이라도 서로 다른 조각으로 본다. 또한 서로 다른 행운의 조각끼리 겹쳐도 된다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어지며, 각 줄에는 대문자 영어 알파벳으로만 이루어진 문자열 S 하나가 들어 있다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 이 테스트 케이스의 텍스트에 있는 서로 다른 행운의 조각의 개수이다.

• 1 ≤ T ≤ 100.
• S는 대문자 영어 알파벳으로만 이루어져 있다.

첫 번째 테스트 케이스에는 행운의 조각이 세 개 있다. 즉 KICKSTARTPROBLEMNAMEDKICKSTART와 KICKSTART 두 번의 등장이다. 두 번째 테스트 케이스의 텍스트에는 행운의 조각이 전혀 없다.