Задано масив з додатних цілих чисел. Його величиною назвемо кількість пар індексів , для яких 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
Приклад 2
Приклад 3
У першому наборі першого прикладу масив дорівнює [10,2,10,3,7,5,25]. Можна видалити числа та : вони не входять у жодну пару з найбільшим спільним дільником, більшим за . Видалити більше двох елементів не можна.
У другому наборі першого прикладу всі числа попарно взаємно прості, тому можна видалити весь масив.
У першому наборі другого прикладу можна видалити обидві шістки: величина масиву зменшиться з до . У другому наборі можна видалити число . У третьому наборі видалення будь-якого елемента прибере дві відповідні пари, тому відповідь дорівнює .
Підзадача ( балів): t\le10, n\le20.
Підзадача ( балів): n\le100, \sum n\le2000.
Підзадача ( балів): n\le1000, \sum n\le20000.
Підзадача ( балів): усі a_i — прості числа.
Підзадача ( балів): без додаткових обмежень.