C. GCD сокровищница
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скупой пират Димаш нашел сокровищницу. Она представляет собой $$$n$$$ кучек монет, пронумерованных от $$$1$$$ до $$$n$$$. В $$$i$$$-й кучке находится ровно $$$a_i$$$ монет. У пирата Димаша есть число $$$x$$$, с помощью которого он может воровать монеты из сокровищницы. Воровство происходит следующим образом:

  • Сначала он выбирает индекс $$$1\le i\le n$$$ такой, что $$$a_i\gt 0$$$ и $$$\gcd$$$$$$^{\text{∗}}$$$$$$(a_i, x) \neq 1$$$. Если таких индексов нет, пират останавливается.
  • Теперь обозначим $$$\gcd(a_i, x)$$$ как $$$g$$$. Пират ворует ровно $$$g$$$ монет из кучки $$$i$$$, после чего $$$a_i$$$ уменьшается на $$$g$$$.
  • Наконец, он приравнивает $$$x$$$ к $$$g$$$ и продолжает воровать монеты.
Ваша задача — помочь пирату своровать максимальное количество монет. Найдите максимальное количество монет, которое можно своровать из сокровищницы.

$$$^{\text{∗}}$$$$$$\gcd(a_i, x)$$$ обозначает наибольший общий делитель (НОД) чисел $$$a_i$$$ и $$$x$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит числа $$$n$$$ и $$$x$$$ ($$$1\le n, x\le 3\cdot 10^5$$$) — количество кучек с монетами в сокровищнице и число пирата.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots a_n$$$ ($$$1 \le a_i \le 3\cdot 10^5$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — максимальное количество монет, которое можно своровать.

Пример
Входные данные
5
3 1
2 3 5
3 4
2 3 4
4 2
2 2 2 2
6 6
2 3 2 3 2 3
7 6
9 9 4 4 4 4 4
Выходные данные
0
6
8
9
20
Примечание

В первом наборе входных данных пират не может ничего своровать.

Во втором наборе входных данных пират ворует следующим образом.

  • Пират выбирает кучку под номером $$$3$$$. Он забирает $$$4$$$ монеты, после чего сокровищница становится $$$[2, 3, 0]$$$, а число $$$x$$$ равным $$$4$$$.
  • Пират выбирает кучку под номером $$$1$$$. Он забирает $$$2$$$ монеты, после чего сокровищница становится $$$[0, 3, 0]$$$, а число $$$x$$$ равным $$$2$$$.
  • Подходящих индексов не осталось, поэтому пират останавливается. Пират смог забрать $$$4 + 2 = 6$$$ монет.