Description

Let X and Y be two given sequences of positive integers $X=( x_1 , x_2 ,\cdots, x_m )$ and $Y=( y_1, y_2 ,\cdots, y_n )$.

A common subsequence of X and Y is a sequence $(x_{i1}=y_{j1},x_{i2}=y_{j2},\cdots,x_{it}=y_{jt})$, where $i1<i2<\cdots<it$ and $j1<j2<\cdots<jt$.

A sequence is called a palindrome if it reads the same forward and backward. For example, the sequence (1, 3, 5, 3, 1) is a palindrome. A common palindromic subsequence of X and Y is a common subsequence of X and Y that is also a palindrome. Among all common palindromic subsequences of X and Y, those with the maximum length are called a longest common palindromic subsequence (LCPS) of X and Y. In general, there may be multiple LCPSs. For example, for the given sequences $X=(1,9,3,9,1)$ and $Y=(1,3,9,3,1)$, the subsequences (1, 3, 1) and (1, 9, 1) are both LCPSs of X and Y.

Our task is: given sequences X and Y, determine the length of a longest common palindromic subsequence.

For the given two sequences $X=( x_1 , x_2 ,\cdots, x_n )$ and $Y=( y_1 , y_2 ,\cdots, y_n )$, compute the length of their longest common palindromic subsequence.

Input Format

The file contains multiple test cases ($\le 10$). For each test case, the first line contains a positive integer $n$ ($1\le n\le 500$), indicating that the lengths of the two input sequences X and Y are both $n$. The next two lines give the input sequences $X=(x_1,x_2,\cdots,x_n)$ and $Y=(y_1,y_2,\cdots, y_n)$, respectively. Each element in the sequences is a positive integer ($\le 20000$). The file ends with a 0.

Output Format

For each test case, output the computed length of the longest common palindromic subsequence, one length per line.

5
1 9 3 9 1
1 3 9 3 1
4
1 9 3 9
1 3 9 3
0

3
1

Hint

Translated by ChatGPT 5