Description

若存在$1≤i _1<i_ 2<…<i_N≤M，1≤j<N$，使$S_j=A_{ij}$且$S_j<S_{j+1}$，则称序列$S _1,S _2,…,S_N$为$A _1,A _2,…,A_M$的上升子序列。若$z$既是$x$的上升子序列，也是$y$的上升子序列，则称$z$是$x$和$y$的公共上升子序列。给定两个整数序列，求两者的最长公共上升子序列的长度。

Format

Input

第$1$行包含测试用例数量$T$。每个测试用例都包含两个序列，对每个序列都用长度$m（1≤m≤500）$和$m$个整数$a_i（-2^{31}≤a_i<2^{31}）$描述。

Output

输出两个序列最长公共上升子序列的长度。

Samples

1
5
1 4 2 5 -12
4
-12 1 2 4

2