All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

Sherlock and Coprime Subset
/

Algorithms, Bitmask, Dynamic Programming

Problem
Editorial
Analytics

Recently Watson learned the concept of coprime numbers and now he wonders given an array A1, A2 . . . AN what is the size of the largest subset of the array such that the each pair of elements in the subset is coprime.

Watson asks Sherlock for help and in turn Sherlock needs you.

Input
First line contains T, the number of test cases.
Each test case contains N in one line, number of elements in the array.
Next line contains N space separated elements A1, A2 . . . AN.

Output
For each test case, output the required answer in one line.

Constraints:
1 ≤ T ≤ 10
25% test data: 1 ≤ N ≤ 10
75% test data: 1 ≤ N ≤ 50
1 ≤ Ai ≤ 50

SAMPLE INPUT
1
5
2 3 2 3 2
SAMPLE OUTPUT
2
Explanation

The largest subset would be taking one of A[0], A[1], A[2] and taking one of A[3], A[4].

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?