Un valor casi inalterado#13123

Un valor casi inalterado

3 segundos
256 megabytes

Se te da un arreglo de enteros positivos. Definimos su valor como la cantidad de pares de índices tales que 1\le i<j\le n y \gcd(a_i,a_j)>1.

Encuentra la máxima cantidad de elementos que se pueden eliminar de modo que el valor del arreglo disminuya a lo sumo en .

Se pueden eliminar todos los elementos. El valor de un arreglo vacío es .

Entrada

La primera línea contiene un entero (1\le t\le10^5) — la cantidad de casos de prueba.

La primera línea de cada caso de prueba contiene un entero (1\le n\le2\cdot10^5) — la longitud del arreglo.

La segunda línea contiene enteros a_1,a_2,\ldots,a_n (1\le a_i\le3\cdot10^5).

La suma de sobre todos los casos de prueba no excede 2\cdot10^5.

Salida

Para cada caso de prueba, imprime un entero — la máxima cantidad de elementos que se pueden eliminar.

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Ejemplo 3

Loading
Loading

Nota

En el primer caso de prueba del primer ejemplo, el arreglo es [10,2,10,3,7,5,25]. Se pueden eliminar y : ninguno de ellos pertenece a un par cuyo máximo común divisor sea mayor que . Es imposible eliminar más de dos elementos.

En el segundo caso de prueba del primer ejemplo, todos los números son coprimos dos a dos, por lo que se puede eliminar todo el arreglo.

En el primer caso de prueba del segundo ejemplo, se pueden eliminar ambos seises: el valor disminuye de a . En el segundo caso de prueba, se puede eliminar el número . En el tercer caso de prueba, eliminar cualquier elemento elimina dos pares que cumplen la condición, por lo que la respuesta es .

Puntuación

  1. Subtarea ( puntos): t\le10, n\le20.

  2. Subtarea ( puntos): n\le100, \sum n\le2000.

  3. Subtarea ( puntos): n\le1000, \sum n\le20000.

  4. Subtarea ( puntos): todos los a_i son primos.

  5. Subtarea ( puntos): sin restricciones adicionales.