TianWang`s Game
If you have any idea about WHU ACM Team, you must know our TianWang, and his untouchable gift and ability, especially in game theory.
This game problem is from him, too. Scared? Aha, go ahead valorously.
Two players are playing this game with 2·N integers alternately. In each round, the player can take one integer away, in this way each player has N integers finally. Every two integers have a GCD (Greatest Common Divisor), so a player would have integer pairs; the sum of all pairs' GCD is his score. The players' goal is to maximize the value his score subtracts his opponent's.
This time, we don't want to know who will win because it's too old; we need the final difference between the two players' score if both of them use the best strategy.
Input
The first line contains a single integer T, indicating the number of test cases. Each test case begins with one integer N(1 ≤ N ≤ 1000), indicating there are 2·N integers for the players. Then 2·N integers A_i (1 ≤ A_i ≤ 1000000) follow, showing the integers.
Output
For each case, output an integer indicating the final difference between the two players' score.