Churu and Balls
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Little Churu is a naughty child, who likes to play with balls. He has N buckets. Each bucket contains one or more balls. He has numbered his buckets 1 to N (both inclusive). He has an infinite supply of extra balls, apart from the ones already in the buckets. He wants to add zero or more number of balls to each of the buckets in such a way, that number of balls in the buckets are in a non-decreasing order, and their GCD is strictly greater than 1.
He wants to do it using the minimum number of extra balls. As he is too young to solve the problem, please help him with the solution.
- First line of input contains an integer T denoting the number of test cases.
- For each test case, first line contains an integer N denoting the number of buckets.
- Second line of each test case contains N space separated integers, where the ith denotes the number of balls in the ith bucket.
For each test case, output a line containing a single integer — the answer for that test case.
Subtask #1: 20 points
- 1 ≤ T ≤ 10, 1 ≤ N ≤ 1000, 1 ≤ number of balls in a bucket ≤ 1000
Subtask #2: 80 points
- 1 ≤ T ≤ 10, 1 ≤ N ≤ 10000, 1 ≤ number of balls in a bucket ≤ 10000
Input: 1 3 11 13 15 Output: 3
Add one ball to each of the buckets.
|Tags||amitpandeykgp, easy, jan16, primenumbers, sieve|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.