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