Cho tập hợp \(A\) gồm \(n\) phần tử. Một tập hợp \(C\) được gọi là tập hợp "VIP" nếu \(C\) thoả mãn các điều kiện sau:

• \(C\) là một tập hợp con của tập hợp \(A\).

• Không tồn tại hai phần tử bất kì nào trong \(C\) là ước của nhau hoặc là bội của nhau.

• \(C\) có số lượng phần tử lớn nhất có thể.

Yêu cầu: Cho tập hợp \(A\). In ra số lượng phần tử của tập hợp \(C\).

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 10)\) - Thể hiện số testcase

• \(t\) block tiếp theo, mỗi block có dạng như sau:

  • Dòng thứ nhất chứa số \(n(1\le n\le 300)\) - Thể hiện số phần tử của mảng \(A\)

  • Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1\le a_i\le 10^{18})\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1\le n\le 20\)

• Subtask \(2\) (\(80\%\) số điểm): Không có điều kiện gì

Example

1
6
2 4 5 6 7 420

4