두 부분 수열 고르기

Clara는 두 문자열 $s$와 $t$를 가지고 있다. Clara는 $s$에서 부분 수열 $x$를, $t$에서 부분 수열 $y$를 골라 다음 조건을 만족시키려고 한다.

• $x$는 $y$보다 사전순으로 작거나 같다.
• $|x| + |y|$가 최대가 된다. 여기서 $|s|$는 문자열 $s$의 길이를 나타낸다.

다음에 유의하자.

• $x$와 $y$는 모두 빈 문자열일 수 있다.
• 부분 수열이란 주어진 수열에서 0개 이상의 원소를 삭제하고 남은 원소의 순서를 유지하여 얻을 수 있는 수열이다.
• 문자열 $x$가 문자열 $y$보다 사전순으로 작다는 것은, $x$가 $y$의 접두사이거나($x \ne y$), $x_i < y_i$이고 모든 $j$ ($1 \le j < i$)에 대해 $x_j = y_j$인 $i$ ($1 \le i \le \min(|x|, |y|)$)가 존재한다는 뜻이다.

입력은 여러 테스트 케이스로 이루어져 있으며, 파일의 끝에서 종료된다. 각 테스트 케이스는 다음과 같다.

첫째 줄에 문자열 $s$가 주어진다. 둘째 줄에 문자열 $t$가 주어진다.

각 테스트 케이스마다 $|x| + |y|$를 출력한다.

• $1 \le |s| \le 2000$
• $1 \le |t| \le 2000$
• $|s|$의 합은 $20000$을 넘지 않는다.
• $|t|$의 합은 $20000$을 넘지 않는다.
• 두 문자열은 영어 소문자로만 이루어져 있다.