Neredeyse Değişmeyen Bir Değer#13123

Neredeyse Değişmeyen Bir Değer

3 saniye
256 megabayt

Size pozitif tam sayıdan oluşan bir dizisi veriliyor. Dizinin değeri olarak 1\le i<j\le n ve \gcd(a_i,a_j)>1 koşullarını sağlayan indeks çiftlerinin sayısını tanımlayalım.

Dizinin değeri en fazla azalacak şekilde silinebilecek maksimum eleman sayısını bulun.

Tüm elemanları silebilirsiniz. Boş dizinin değeri 'dır.

Giriş

İlk satırda bir tam sayı (1\le t\le10^5) — test durumlarının sayısı verilir.

Her test durumunun ilk satırında bir tam sayı (1\le n\le2\cdot10^5) — dizinin uzunluğu verilir.

İkinci satırda tam sayı a_1,a_2,\ldots,a_n (1\le a_i\le3\cdot10^5) verilir.

Tüm test durumları üzerinden değerlerinin toplamı 2\cdot10^5'i aşmaz.

Çıktı

Her test durumu için silinebilecek maksimum eleman sayısını — tek bir tam sayı olarak yazdırın.

Örnekler

Örnek 1

Loading
Loading

Örnek 2

Loading
Loading

Örnek 3

Loading
Loading

Not

Birinci örneğin ilk test durumunda dizi [10,2,10,3,7,5,25]'tir. ve sayıları silinebilir: hiçbiri en büyük ortak böleni 'den büyük olan bir çifte ait değildir. İkiden fazla eleman silmek mümkün değildir.

Birinci örneğin ikinci test durumunda tüm sayılar ikişer ikişer aralarında asaldır, bu nedenle dizinin tamamı silinebilir.

İkinci örneğin ilk test durumunda her iki altı da silinebilir: dizinin değeri 'den 'a düşer. İkinci test durumunda sayısı silinebilir. Üçüncü test durumunda herhangi bir elemanın silinmesi koşulu sağlayan iki çifti ortadan kaldırır, bu nedenle cevap 'dır.

Puanlama

  1. Alt görev ( puan): t\le10, n\le20.

  2. Alt görev ( puan): n\le100, \sum n\le2000.

  3. Alt görev ( puan): n\le1000, \sum n\le20000.

  4. Alt görev ( puan): tüm a_i sayıları asaldır.

  5. Alt görev ( puan): ek kısıtlama yoktur.