Kick_Start

크세니아는 독서를 매우 좋아해서, 매일 아침 나머지 일과를 시작하기 전에 자신이 가장 좋아하는 책의 한 구간을 읽으며 하루를 시작한다. 구간은 단순히 텍스트의 부분 문자열이다. 크세니아는 다소 미신을 믿으며, 자신이 읽는 구간이 문자열 KICK로 시작하고, 이어서 0개 이상의 문자가 나온 뒤, 최종적으로 문자열 START로 끝나면 전체 구간의 내용이 별 의미가 없더라도 그날 운이 좋을 것이라고 믿는다.

책의 텍스트가 주어질 때, 책이 낡아 새 책을 사야 하기 전까지 크세니아가 읽을 수 있는 서로 다른 행운의 구간 수를 구하라. 두 구간이 텍스트의 서로 다른 위치에서 시작하거나 끝난다면, 읽히는 내용이 같더라도 서로 다른 구간으로 간주한다. 또한 서로 다른 행운의 구간은 겹칠 수도 있음에 유의하라.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. S는 영문 대문자로만 이루어진다.

테스트 세트 1

시간 제한: 20초. 1 ≤ |S| ≤ 1000.

테스트 세트 2

시간 제한: 40초. 1 ≤ |S| ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에는 각각 영문 대문자로만 이루어진 하나의 문자열 S가 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 해당 테스트 케이스의 텍스트에 있는 서로 다른 행운의 구간 수이다.

첫 번째 테스트 케이스에는 세 개의 행운의 구간이 있으며, 구체적으로 KICKSTARTPROBLEMNAMEDKICKSTART 하나와 KICKSTART 두 개이다. 두 번째 테스트 케이스의 텍스트에는 행운의 구간이 전혀 없다.