문제

문자열 가 주어진다. 길이는 이다. 길이가 인 접두사(Prefix)는 이고, 길이가 인 접미사(Suffix)는 이다.

길이가 인 문자열이 동시에 의 접두사이자 접미사이면, 이를 경계(Border) 라고 한다.

모든 경계 문자열에 대해, 해당 문자열이 의 부분 문자열로 몇 번 등장하는지 구할 수 있다.

정수 가 주어질 때, 각 쿼리 에 대해

부분 문자열로 최소 번 이상 등장하는 경계의 개수

를 출력하라.

같은 내용의 문자열이라도 길이가 다르면 다른 경계로 센다.

입력

• 첫 줄에 문자열 가 주어진다. (영문 소문자, )
• 둘째 줄에 정수 가 주어진다. ()
• 셋째 줄부터 줄에 걸쳐, 각 줄에 정수 가 주어진다. ()

출력

각 쿼리마다 한 줄에 하나씩 결과를 출력한다.