Coders

  You are given an array   A = [ A 1 , A 2 , … , A N ] A = [ A 1 , A 2 , … , A N ]  containing  distinct positive  integers. Let  B B  be a  permutation  of  A A . Define the  value  of  B B  to be ∑ i = 1 N ( B i mod B i + 1 ) ∑ i = 1 N ( B i mod B i + 1 ) where  B N + 1 B N + 1  is treated to be  B 1 B 1 . Find the  maximum   value  across all permutations of  A A . Input Format The first line of input contains a single integer  T T , denoting the number of test cases. The description of  T T  test cases follows. Each test case consists of two lines of input. The first line of each test case contains an integer  N N  — the size of  A A . The second line of each test case contains  N N  space-separated integers — the elements of  A A . Output Format For each test case, output a new line containing the answer — the maximum possible value across all permutations of  A A . Constraints 1 ≤ T ≤ 10 3 1 ≤ T ≤ 10 3 2 ≤ N ≤ 2 ⋅ 10 3 2 ≤ N ≤ 2 ⋅ 10 3 1 ≤ A i ≤ 10 15 1 ≤ A i ≤ 10 15 A i ≠ A j A