La FIFA dio a conocer que la sede de la Copa Mundial de Futbol 3018 sera en Kazakhstan, tambien anuncio el cambio de su sistema de clasificacion para el Mundial, la clasificacion sera de forma directa y consiste de la siguiente forma:

• Se Inscribiran N selecciones y cada una de estas selecciones tiene un identificador unico de 1 a N.
• Se escogera una lista de numeros de tamaño M ,se garantiza que esta lista solo contendra numeros primos que a su vez seran unicos en la lista.
• Una Seleccion obtiene la clasificacion directa si su identificador es multiplo de al menos un numero de la lista M.

Con este cambio en el sistema de clasificacion la FIFA desea conocer cuantas selecciones clasificarian directamente al Mundial.

La primera linea de entrada consiste en el numero de casos de prueba T donde 1<=T<=1000.
Por cada caso de prueba habra un entero N (selecciones Inscritas) donde 1<=N<=10¹⁸, seguido un entero M (tamaño de la lista) donde 1<=M<=15, finalmente M numeros primos.

Imprimir por cada caso de prueba el numero de selecciones clasificadas.

Competencia Interna 2da Division UMSA 2018