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 ≤ c_{i+1}\) (\(i = 1, 2, \dots, k - 1\)).

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

• Ghi 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.

Giới hạn

• 30% số test có \(m, n \le 15\).
• 30% số test khác có \(m, n \le 150\).
• Có 40% số test còn lại có \(m, n \le 1500\).

Input 1

1
5 5
5 1 6 10 20
1 8 6 10 20

Output 1

3