题目描述

设 X 和 Y 是2个给定的正整数序列 $X=( x_1 , x_2 ,\cdots, x_m )$和$Y=( y_1, y_2 ,\cdots, y_n )$。

X 和 Y的一个公共子序列是指X 和 Y的一个公共子序列$(x_{i1}=y_{j1},x_{i2}=y_{j2},\cdots,x_{it}=y_{jt})$, 其中 $i1<i2<\cdots<it$ 。

当一个序列正读和反读都相同时，称该序列是回文。例如，序列$(1,3,5,3,1)$就是回文。 X 和 Y的一个公共回文子序列是指X 和 Y的一个公共子序列，且该子序列是回文。 在X 和 Y的所有公共回文子序列中，长度最长的就称为X 和 Y的一个最长公共回文子序列。在一般情况下， X 和 Y会有多个最长公共回文子

序列。例如，对于给定的正整数序列$X=(1,9,3,9,1)$ 和 $Y=(1,3,9,3,1)$，其子序列$(1,3,1)$和$(1,9,1)$都是X 和 Y的最长公共回文子序列。

我们的问题是，对于给定的正整数序列X 和 Y，确定其最长公共回文子序列的长度。

对于给定的2个正整数序列$X=( x_1 , x_2 ,\cdots, x_n )$和$Y=( y_1 , y_2 ,\cdots, y_n )$，计算出它们的最长公共回文子序列的长度。

输入格式

文件有多个测试项（$\le 10$）。每个测试项的第一行有1个正整数$n$， ($1\le n\le 500$)，表示2个输入序列X和Y的长度均为$n$。接下来的2行分别给出输入正整数序列$X=(x_1,x_2,\cdots,x_n)$和$Y=(y_1,y_2,\cdots, y_n)$。其中序列中每个元素均为正整数（ $\le 20000$）。文件最后以一个0结束。

输出格式

将计算出的每个测试项的最长公共回文子序列的长度依次输出到文件中， 每行输出一个长度。

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

3
1