Juki entro recien a la secundaria, y justo en sus clases de matematicas aprendio a identificar a los numeros primos, un numero primo es aquel que tiene unicamente $2$ divisores.

Los primeros números primos son: $[2, 3, 5, 7, 11, 13, ...]$.

Al profesor de Juki le fascinan los numeros primos, asi que les dio la siguiente tarea:

Deben listar todos los numeros primos que sean menores o iguales a $10^7$, y ponerlos en una lista, donde el primer numero primo, le cual es el $2$ estaria en la posicion $0$, el número $3$ en la posicion $1$, asi sucesivamente.

Luego de listar, deben empezar a sumar todos los números primos empezando desde la posicion $0$ mientras sea menor o igual a un número $x$ , pero Juki cuando empieza a sumar, se concentra en sumar que pierde la nocion respecto a los numeros primos, y pues varias veces se ha pasado del limite  que puso el profesor, asi que ahora te pide ayuda para que le digas en que posición debe terminar de sumar.

La primera linea tiene un numero entero $q$ ($ 1 \leq q \leq 10^5$), que indica la cantidad de preguntas que les hace el profesor.

Luego vienen $q$ lineas, cada linea tiene un número entero $x$ ($ 1 \leq x \leq 10^{18}$, el cual es el limite de la suma que juki debe hacer

Para cada consulta debe imprimir $2$ números enteros, la posicion de la lista donde debe terminar.