Ghép cặp hoàn hảo

Trong một dự án mới, FullHouse Dev được giao nhiệm vụ phát triển một thuật toán ghép cặp cho một công ty mai mối. Thuật toán này, mặc dù đơn giản và có vẻ không hợp lý, lại mang lại hiệu quả bất ngờ. FullHouse Dev quyết định nghiên cứu sâu hơn về thuật toán này để tối ưu hóa hiệu suất của nó.

Bài toán

Cho \(n\) cặp nam nữ. Danh sách ban đầu của nam và nữ được sắp xếp ngẫu nhiên. Sau đó, danh sách nữ được sắp xếp theo chiều cao tăng dần, còn danh sách nam theo chiều cao giảm dần. Một cặp được coi là "lý tưởng" nếu chiều cao của người này chia hết cho chiều cao của người kia hoặc ngược lại. Nhiệm vụ của FullHouse Dev là xác định số lượng cặp lý tưởng có thể được tạo ra.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Dòng đầu tiên của mỗi test case chứa số nguyên \(n\) - số lượng nam/nữ.
• Dòng thứ hai chứa \(n\) số nguyên - chiều cao của các nữ.
• Dòng thứ ba chứa \(n\) số nguyên - chiều cao của các nam.

OUTPUT FORMAT:

• Với mỗi test case, in ra số lượng cặp lý tưởng.

Ràng buộc:

• \(1 \leq T \leq 10^2\)
• \(1 \leq n \leq 10^4\)
• \(1 \leq A_i, B_i \leq 10^5\) (với \(A_i\) là chiều cao của nữ thứ \(i\) và \(B_i\) là chiều cao của nam thứ \(i\))

Ví dụ

INPUT

2
4
1 6 9 12
4 12 3 9
4
2 2 2 2
2 2 2 2

OUTPUT

2
4

Giải thích

• Ở test case đầu tiên, sau khi sắp xếp, các cặp sẽ là (12,12), (9,9), (6,4), (1,3). Có 2 cặp lý tưởng là (12,12) và (9,9).
• Ở test case thứ hai, tất cả các cặp đều lý tưởng vì chiều cao bằng nhau, nên kết quả là 4.

FullHouse Dev nhận ra rằng thuật toán này, mặc dù đơn giản, có thể được tối ưu hóa và mở rộng để áp dụng cho nhiều trường hợp phức tạp hơn trong tương lai.