뒤섞인 단어

Scrmable 교수는 자신이 검토하던 논문에서 철자 오류를 발견했지만, 단어를 읽고 이해하는 데에는 어려움이 없었다. 조사를 해 보던 그녀는 아래와 같이 설명된 흥미로운 글을 발견했다.

영국의 한 대학에서 수행한 연구에 따르면, 단어 안에서 글자가 어떤 순서로 놓이는지는 중요하지 않고 첫 글자와 마지막 글자만 올바른 자리에 있으면 된다. 나머지는 완전히 뒤죽박죽이어도 문제없이 읽을 수 있다. 인간의 뇌는 글자를 하나하나 읽는 것이 아니라 단어 전체를 읽기 때문이다.

아니면 이런 식으로 ...

Aoccdrnig to a study at an Elingsh uinervtisy, it deosn't mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteer be at the corecrt pclae. The rset can be a toatl mses and you can sitll raed it wouthit a porbelm. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.

Scrmable 교수는 이 개념을 더 파고들기 위해 비슷하게 뒤섞인 단어들로 이루어진 여러 문장을 모아 인기 있는 출판물에 보내기로 했다. 안타깝게도 교수의 키보드에서 스페이스 키가 작동하지 않아, 그녀는 하나의 긴 문자열을 만들어 냈다. 그녀는 사전에 있는 단어 중 원래 형태이든 뒤섞인 형태이든 긴 문자열에 부분 문자열로 (적어도 한 번) 나타나는 단어의 수를 구해 달라고 부탁했다. (뒤섞인 형태란 같은 글자 집합으로 이루어지고 첫 글자와 마지막 글자의 위치가 같으며, 나머지 글자는 임의의 순서로 놓인 형태를 말한다.)

사전의 단어는 문자열에 여러 번 나타날 수 있지만, 적어도 한 번 나타나는지만 알면 되므로 한 번만 세야 한다. 예를 들어 사전에 this라는 단어가 있다면, 세어지는 유효한 단어는 this (원래 형태)와 tihs (뒤섞인 형태)이고, tsih, siht 및 다른 변형들은 t로 시작해 s로 끝나지 않으므로 유효하지 않다. 또한 tis, tiss, thiss는 원래 글자 집합을 재배열한 것이 아니므로 뒤섞인 형태가 아니다.

교수는 매우 바쁘기 때문에 이 일을 가장 아끼고 신뢰하는 연구 조교인 당신에게 맡긴다. 사전이 주어졌을 때, 사전의 단어 중 교수의 문자열에 원래 형태이든 뒤섞인 형태이든 적어도 한 번 부분 문자열로 나타나는 단어의 수를 구할 수 있는가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 세 줄로 이루어진다. 첫 줄에는 정수 L이 주어진다. 둘째 줄에는 소문자 영어 알파벳으로 이루어진 L개의 단어가 주어지며, 이것이 사전을 구성한다. 셋째 줄에는 소문자 영어 알파벳 S1과 S2, 그리고 다섯 개의 정수 N, A, B, C, D가 주어진다. S1과 S2는 교수의 문자열 S의 처음 두 글자이고, N은 S의 길이이며, 나머지 네 정수는 아래와 같이 S의 글자를 생성하는 데 사용하는 매개변수이다.

먼저 ord(c)를 문자 c의 십진수 값, char(n)을 십진수 n의 문자 값으로 정의한다. 예를 들어 ord('a') = 97이고 char(97) = 'a'이다. 다른 변환은 ASCII 표를 참고하면 된다. 이제 x1 = ord(S1), x2 = ord(S2)로 정의한다. 그런 다음 아래의 점화식을 사용해 i = 3부터 N까지 xi를 생성한다.

• xi = ( A * xi-1 + B * xi-2 + C ) modulo D.

i = 3부터 N까지 Si = char(97 + ( xi modulo 26 ))으로 정의한다.

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호 (1부터 시작)이고, y는 사전의 단어 중 주어진 문자열에 (위에서 정의한 대로 원래 형태이거나 뒤섞인 형태로) 부분 문자열로 나타나는 단어의 수이다.

• 1 ≤ T ≤ 20.
• 사전의 두 단어는 서로 같지 않다.
• 사전의 각 단어는 2글자 이상 105글자 이하이다.
• 사전에 있는 모든 단어의 길이 합은 105를 넘지 않는다.
• S1과 S2는 소문자 영어 알파벳이다.
• 0 ≤ A ≤ 109.
• 0 ≤ B ≤ 109.
• 0 ≤ C ≤ 109.
• 1 ≤ D ≤ 109.

샘플 케이스 #1에서 생성 방법을 사용하면 생성된 문자열 S는 aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt이다. 사전 단어의 뒤섞인 형태나 원래 형태가 다음과 같이 나타난다.

• axpaj는 뒤섞인 형태로 aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt에 나타난다.
• apxaj는 뒤섞인 형태로 aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt에 나타난다. apxaj가 다른 사전 단어 axpaj의 뒤섞인 형태이더라도 둘 다 세야 한다.
• dnrbt는 원래 형태로 aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt에 두 번 나타나지만, 한 번만 세야 한다.
• pjxdn은 뒤섞인 형태로 aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt에 나타난다. 이 출현은 다른 사전 단어의 출현과 겹치지만, 둘은 각각 독립적으로 센다.
• abd는 전혀 나타나지 않는다.

참고: 이 문제의 대규모 데이터셋에는 인터프리터 언어나 느린 언어를 사용하지 않는 것이 좋다.