Chef and Kites
After celebrating Holi, Chef decided to solve a problem. He has N Kites, each has a number written on it. The i-th kite has number A[i] written on it. He wants to tie all the kites, so that when he puts one kite in air, all others are also in air. To tie i-th and j-th kite, it takes effort of min(A[i] % A[j], A[j] % A[i]). Everyone wants to do their work with minimum effort, Chef is no other person.
Help Chef to find out the minimum effort to tie all kites.
First line of input contains T, number of test cases.
T lines follow,
First line of each test case contains N, number of kites.
Second line of each test case contains A, A, ..., A[N] space separated.
Output consists of T lines, i-th line containing the answer to i-th test case.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 10^5
- 1 ≤ A[i] ≤ 10^5
Input: 3 4 2 6 3 11 4 1 2 3 4 3 4 9 15 Output: 1 0 4
|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, CLOJ, FS|
Fetching successful submissions