Dãy con chung bội hai dài nhất

Dãy $C=c_1,c_2,\dots ,c_k$ được gọi là dãy con của dãy $A=a_1,a_2,\dots ,a_n$ nếu $C$ có thể nhận được bằng cách xóa bớt một số phần tử của dãy $A$ và giữ nguyên thứ tự của các phần tử còn lại, nghĩa là tìm được dãy các chỉ số $1\le l_1<l_2<\dots <l_k\le n$ sao cho $c_1=a_{l_1},c_2=a_{l_2},\dots ,c_k=a_{l_k}$. Ta gọi độ dài của dãy là số phần tử của dãy.

Cho hai dãy $A=a_1,a_2,\dots ,a_m$ và $B=b_1,b_2,\dots ,b_n$. Dãy $C=c_1,c_2,\dots ,c_k$ được gọi là dãy con chung bội hai của dãy $A$ và $B$ nếu $C$ vừa là dãy con của dãy $A$, vừa là dãy con của dãy $B$ và thỏa mãn điều kiện $2\times c_i\le c_{i+1}$ ($i=1,2,\dots ,k-1$).

Yêu cầu: Cho hai dãy $A$ và $B$. Hãy tìm độ dài dãy con chung bội hai có độ dài lớn nhất của hai dãy $A$ và $B$.

Dữ liệu vào

Dòng đầu tiên chứa $T$ là số lượng bộ dữ liệu. Tiếp đến là $T$ nhóm dòng, mỗi nhóm cho thông tin về một bộ dữ liệu theo khuôn dạng sau:

• Dòng đầu chứa $2$ số nguyên dương $m$ và $n$.
• Dòng thứ hai chứa $m$ số nguyên không âm $a_1,a_2,\dots ,a_m$, mỗi số không vượt quá ${10}^9$.
• Dòng thứ ba chứa $n$ số nguyên không âm $b_1,b_2,\dots ,b_n$, mỗi số không vượt quá ${10}^9$.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra

In ra $T$ dòng, mỗi dòng ghi một số nguyên là độ dài dãy con chung bội hai dài nhất của dãy $A$ và $B$ tương ứng với bộ dữ liệu vào (in $0$ nếu hai dãy không có phần tử chung).

Ràng buộc

• $1\le T\le 10$.
• $1\le m,n\le 1500$.
• $0\le a_i,b_j\le {10}^9$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $m,n\le 15$.
• Subtask 2 ($30\%$ số điểm): $m,n\le 150$.
• Subtask 3 ($40\%$ số điểm): $m,n\le 1500$.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ