Dãy \(C = c_1, c_2,..., c_k\) được gọi là dãy con của dãy \(A = a_1, a_2,..., 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 \leq l_1 < l_2 < ... < l_k \leq n\) sao cho \(c_1 = a_{l_1}\), \(c_2 = a_{l_2}\),..., \(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,..., a_m\) và \(B = b_1, b_2,..., b_n\). Dãy \(C = c_1, c_2,..., 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 * c_i ≤ c_{i+1}\) (\(i = 1, 2,..., 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\).

Input

• 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\), ..., \(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\), ..., \(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.

Output

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

Scoring

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

Example

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

3