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.
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.
Hər test halı üçün bir tam ədəd — silinə bilən elementlərin maksimum sayını çap edin.
Nümunə 1
Nümunə 2
Nümunə 3
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.
Alt tapşırıq ( bal): t\le10, n\le20.
Alt tapşırıq ( bal): n\le100, \sum n\le2000.
Alt tapşırıq ( bal): n\le1000, \sum n\le20000.
Alt tapşırıq ( bal): bütün a_i ədədləri sadədir.
Alt tapşırıq ( bal): əlavə məhdudiyyət yoxdur.