Minimum Deletions

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
The *greatest common divisor* (GCD) of a sequence is the greatest positive integer which divides each element of this sequence. You are given a sequence $A$ of positive integers with size $N$. You are allowed to delete up to $N1$ elements from this sequence. (I.e., you may delete any number of elements, including zero, as long as the resulting sequence is nonempty.) Please find the minimum number of elements which have to be deleted so that the GCD of the resulting sequence would be equal to $1$, or determine that it is impossible. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \dots, A_N$. ### Output For each test case, print a single line containing one integer — the minimum number of elements to delete, or $1$ if it is impossible to make the GCD equal to $1$. ### Constraints  $1 \le T \le 100$  $2 \le N \le 1,000$  $1 \le A_i \le 50,000$ for each valid $i$ ### Subtasks **Subtask #1 (20 points):** $2 \le N \le 3$ **Subtask #2 (80 points):** original constraints ### Example Input ``` 2 2 2 3 2 2 4 ``` ### Example Output ``` 0 1 ``` ### Explanation **Example case 1:** The GCD is already equal to $1$, so the answer is $0$. **Example case 2:** It is impossible to make the GCD equal to $1$, so the answer is $1$.Author:  nileshjha19 
Editorial  https://discuss.codechef.com/problems/RD19 
Tags  cakewalk, gcd, may18, nileshjha19 
Date Added:  2042018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 