Demək olar ki, dəyişməyən qiymət#13123

Demək olar ki, dəyişməyən qiymət

3 saniyə
256 meqabayt

müsbət tam ədəddən ibarət massivi verilir. Massivin qiyməti 1\le i<j\le n və \gcd(a_i,a_j)>1 şərtlərini ödəyən indeks cütlərinin sayı adlanır.

Massivin qiymətini ən çox azaltmaqla silinə bilən elementlərin maksimum sayını tapın.

Bütün elementləri silmək olar. Boş massivin qiyməti -dır.

Giriş

Birinci sətirdə bir tam ədəd (1\le t\le10^5) — test hallarının sayı verilir.

Hər test halının birinci sətrində bir tam ədəd (1\le n\le2\cdot10^5) — massivin uzunluğu verilir.

İkinci sətirdə tam ədəd a_1,a_2,\ldots,a_n (1\le a_i\le3\cdot10^5) verilir.

Bütün test halları üzrə qiymətlərinin cəmi 2\cdot10^5-i keçmir.

Çıxış

Hər test halı üçün bir tam ədəd — silinə bilən elementlərin maksimum sayını çap edin.

Nümunələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading

Nümunə 3

Loading
Loading

Qeyd

Birinci nümunənin birinci test halında massiv [10,2,10,3,7,5,25]-dir. və ədədlərini silmək olar: onlar ən böyük ortaq böləni -dən böyük olan heç bir cütə daxil deyillər. İkidən çox element silmək mümkün deyil.

Birinci nümunənin ikinci test halında bütün ədədlər cüt-cüt qarşılıqlı sadədir, buna görə bütün massivi silmək olar.

İkinci nümunənin birinci test halında hər iki altını silmək olar: massivin qiyməti -dən -a enir. İkinci test halında ədədini silmək olar. Üçüncü test halında istənilən elementin silinməsi iki uyğun cütü aradan qaldırır, buna görə cavab -dır.

Bal hesablama

  1. Alt tapşırıq ( bal): t\le10, n\le20.

  2. Alt tapşırıq ( bal): n\le100, \sum n\le2000.

  3. Alt tapşırıq ( bal): n\le1000, \sum n\le20000.

  4. Alt tapşırıq ( bal): bütün a_i ədədləri sadədir.

  5. Alt tapşırıq ( bal): əlavə məhdudiyyət yoxdur.