게놈 진화

발생생물학자 Xi는 염색체 사이의 발생 거리를 연구한다. Xi의 단순한 모형에서 염색체 하나는 $1$번부터 $n$번까지 번호를 붙인 유전자 $n$개의 순열이다. Xi는 염색체 두 개 사이의 진화 거리를 재는 척도를 만들고 있다. Xi의 진화 이론에서는 두 염색체 모두에서 서로 붙어 있는 유전자 집합이 두 염색체가 비슷하다는 긍정 증거다.

긍정 증거는 길이가 같은 두 수열 $A$와 $A'$의 쌍이다. $A$는 첫 번째 염색체의 연속한 부분 수열이고, $A'$는 두 번째 염색체의 연속한 부분 수열이며, $A$는 $A'$의 순열이다. 두 염색체 모두 유전자를 한 번씩만 담으므로 $A$가 정해지면 짝이 되는 $A'$는 많아야 하나다. 주어진 두 염색체에서 길이가 $1$보다 큰 긍정 증거가 몇 개인지 세어라.

입력은 테스트 케이스 여러 개로 이루어진다. 각 테스트 케이스의 첫 줄에는 유전자의 개수 $n$이 주어진다 ($2 \le n \le 3000$). 다음 두 줄에는 염색체 두 개가 한 줄에 하나씩 양의 정수 목록으로 주어지고, 각 줄은 $1$부터 $n$까지의 수를 정확히 한 번씩 담는다. 마지막 줄에는 $0$이 하나 주어지며, 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 두 염색체의 긍정 증거 개수를 한 줄에 출력한다.