E1. Простое наводнение (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии $$$1 \le n \le 3000$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Антиган и Ламус затопили дом Мадамант. Она хочет, чтобы они выровняли уровни воды, удалив как можно меньше воды.

Формально, начальные уровни воды заданы массивом $$$a = [a_1, a_2, \ldots, a_n]$$$. Для каждого возможного устранения последствий Антиган и Ламус выбирают непустую подпоследовательность$$$^{\text{∗}}$$$ $$$b$$$ массива $$$a$$$. Они могут выполнить следующую операцию над $$$b$$$ любое количество раз, возможно, ноль:

  • выбрать простое число $$$p$$$;
  • одновременно уменьшить каждый элемент $$$b_i$$$, текущее значение которого делится на $$$p$$$, на $$$1$$$. Все остальные элементы остаются неизменными.

Пусть $$$f(b)$$$ — наибольшее целое число $$$x$$$, такое что после некоторой последовательности операций каждый элемент $$$b$$$ равен $$$x$$$.

Найдите сумму $$$f(b)$$$ по всем непустым подпоследовательностям $$$b$$$ массива $$$a$$$ по модулю $$$998\,244\,353$$$. Подпоследовательности, образованные разными наборами индексов, учитываются отдельно, даже если их значения совпадают.

Каждая подпоследовательность рассматривается независимо, начиная со своих исходных значений.

$$$^{\text{∗}}$$$Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 3000$$$) — длина массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3000$$$.

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

Для каждого набора входных данных выведите одно целое число — сумму $$$f(b)$$$ по всем непустым подпоследовательностям $$$b$$$ массива $$$a$$$ по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4
1
1
4
2 4 4 4
4
2 3 4 4
6
3 6 1 1 1 1
Выходные данные
1
37
34
72
Примечание

В первом наборе входных данных единственная непустая подпоследовательность равна $$$[1]$$$, и выполнять операции не требуется. Поэтому её вклад равен $$$f([1]) = 1$$$.

Во втором наборе входных данных $$$2^3 - 1 = 7$$$ непустых подпоследовательностей, содержащих только вхождения $$$4$$$, дают вклад $$$4 \cdot 7 = 28$$$. Подпоследовательность $$$[2]$$$ даёт вклад $$$2$$$. Для каждой из $$$7$$$ подпоследовательностей, содержащих значение $$$2$$$ и хотя бы одно вхождение $$$4$$$, выполняется $$$f(b) = 1$$$. Следовательно, ответ равен $$$28 + 2 + 7 = 37$$$.