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

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, \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.

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.

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

Sample Input

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

Sample Output

3