Гра TianWang`а
Якщо ви знайомі з командою WHU ACM, то, напевно, знаєте нашого ТяньВана та його неперевершений талант і здібності, особливо в теорії ігор.
Ця задача з гри також від нього. Злякалися? Ага, сміливо вперед.
Два гравці грають у цю гру з 2·N цілими числами по черзі. У кожному раунді гравець може забрати одне ціле число, таким чином, кожен гравець в кінці має N цілих чисел. Кожна пара цілих чисел має НСД (Найбільший Спільний Дільник), тому у гравця будуть пари цілих чисел; сума всіх НСД пар є його рахунком. Мета гравців — максимізувати різницю між своїм рахунком та рахунком суперника.
Цього разу ми не хочемо знати, хто переможе, бо це занадто передбачувано; нам потрібна кінцева різниця між рахунками двох гравців, якщо обидва використовують найкращу стратегію.
Вхідні дані
Перша строка містить одне ціле число T, що вказує на кількість тестових випадків. Кожен тестовий випадок починається з одного цілого числа N (1 ≤ N ≤ 1000), що вказує, що є 2·N цілих чисел для гравців. Далі йдуть 2·N цілих чисел A_i (1 ≤ A_i ≤ 1000000), що представляють цілі числа.
Вихідні дані
Для кожного випадку виведіть ціле число, що вказує на кінцеву різницю між рахунками двох гравців.