Майже незмінна величина#13123

Майже незмінна величина

3 секунди
256 мегабайтів

Задано масив з додатних цілих чисел. Його величиною назвемо кількість пар індексів , для яких 1\le i<j\le n та \gcd(a_i,a_j)>1.

Знайдіть максимальну кількість елементів, які можна видалити з масиву так, щоб його величина зменшилася не більш як на .

Можна видалити всі елементи. Величина порожнього масиву дорівнює .

Вхідні дані

Перший рядок містить ціле число (1\le t\le10^5) — кількість наборів вхідних даних.

Перший рядок кожного набору містить ціле число (1\le n\le2\cdot10^5) — кількість елементів масиву.

Другий рядок містить цілих чисел a_1,a_2,\ldots,a_n (1\le a_i\le3\cdot10^5).

Гарантується, що сума за всіма наборами вхідних даних не перевищує 2\cdot10^5.

Вихідні дані

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

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

У першому наборі першого прикладу масив дорівнює [10,2,10,3,7,5,25]. Можна видалити числа та : вони не входять у жодну пару з найбільшим спільним дільником, більшим за . Видалити більше двох елементів не можна.

У другому наборі першого прикладу всі числа попарно взаємно прості, тому можна видалити весь масив.

У першому наборі другого прикладу можна видалити обидві шістки: величина масиву зменшиться з до . У другому наборі можна видалити число . У третьому наборі видалення будь-якого елемента прибере дві відповідні пари, тому відповідь дорівнює .

Оцінювання

  1. Підзадача ( балів): t\le10, n\le20.

  2. Підзадача ( балів): n\le100, \sum n\le2000.

  3. Підзадача ( балів): n\le1000, \sum n\le20000.

  4. Підзадача ( балів): усі a_i — прості числа.

  5. Підзадача ( балів): без додаткових обмежень.