Игра TianWang
Если вы знакомы с командой WHU ACM, то наверняка слышали о нашем ТяньВане и его выдающихся талантах, особенно в теории игр.
Эта задача игры также от него. Испугались? Нет? Тогда продолжайте.
Два игрока поочередно играют с 2·N целыми числами. В каждом ходе игрок может взять одно число, так что в конце у каждого будет N чисел. Каждая пара чисел имеет НОД (Наибольший Общий Делитель), и у игрока будут пары чисел; сумма всех НОД пар составляет его счет. Цель игроков — максимизировать разницу между своим счетом и счетом соперника.
На этот раз мы не хотим знать, кто победит, так как это слишком банально; нас интересует окончательная разница между счетами двух игроков, если оба используют наилучшую стратегию.
Входные данные
Первая строка содержит одно целое число T, обозначающее количество тестов. Каждый тест начинается с одного целого числа N (1 ≤ N ≤ 1000), обозначающего, что у игроков есть 2·N целых чисел. Далее следуют 2·N целых чисел A_i (1 ≤ A_i ≤ 1000000), представляющих числа.
Выходные данные
Для каждого теста выведите одно целое число, обозначающее окончательную разницу между счетами двух игроков.