팔찌

메가마인드가 마침내 숙적 메트로 맨을 쓰러뜨릴 완벽한 계획을 세웠다. 그는 왼쪽과 오른쪽 손목에 찰 원형 능력 팔찌 한 쌍을 만들었다. 각 팔찌에는 마법 글리프(기호)가 한 줄로 새겨져 있으며, 활성화된 글리프 하나마다 메가마인드의 힘이 회색곰 한 마리만큼 세진다.

그런데 조건이 있다. 두 팔찌는 각 팔찌에서 활성화한 글리프들의 부분수열이 서로 완전히 같을 때에만 작동한다. 예를 들어 두 팔찌의 글리프가 각각 문자열 “metrocity”와 “kryptonite”로 주어졌다면, 최적으로 글리프를 활성화하면 메가마인드는 회색곰 10마리의 힘을 얻는다. 첫 번째 팔찌에서는 “etoty”가 시계 방향 순서로 활성화되고, 두 번째 팔찌에서는 같은 글자들이 반시계 방향 순서로 활성화된다. 이때 각 팔찌마다 글리프 5개가 활성화되므로 힘은 $5 + 5 = 10$이 된다.

일반적으로 활성화한 글자들의 순서는 중요하지만, 각 팔찌에서 부분수열을 읽는 방향(시계 방향인지 반시계 방향인지)은 두 팔찌가 서로 같을 수도 있고 다를 수도 있다. 또한 팔찌가 원형이라는 점을 잊지 말자. 즉 어느 위치에서 시작해 읽어도 된다.

두 팔찌를 활성화해 메가마인드가 얻을 수 있는 최대 힘(회색곰 마리 수)을 구하라.

입력은 여러 개의 테스트 케이스로 이루어지며, 최대 100개(그중 “큰” 테스트 케이스는 최대 5개)까지 주어진다. 각 테스트 케이스는 한 줄에 공백으로 구분된 두 문자열 $s$와 $t$로 주어지며, 각각 메가마인드의 왼쪽 팔찌와 오른쪽 팔찌에 새겨진 글리프 나열을 나타낸다. 두 문자열은 모두 소문자 영어 알파벳(‘a’–‘z’)으로만 이루어진다. 각 문자열의 길이는 $1$ 이상 $100$ 이하이며, “큰” 테스트 케이스에서는 $1$ 이상 $1500$ 이하이다. 입력은 파일의 끝까지 계속된다.

각 테스트 케이스마다, 두 팔찌의 글리프를 활성화해 얻을 수 있는 최대 힘(회색곰 마리 수)을 한 줄에 하나씩 출력한다.