Matias y sus amigos viven a las afueras de la ciudad cerca de una vieja fabrica de autos abandonda, Matias es un niño muy travieso pero a la vez muy listo, Él y sus amigos visitaron la fabrica abandonada, para lo único que podian hacer. Jugar.

En un recorrido bastante aburrido Matias encontro un aparato mecánico que tenía una bandeja con N objetos metálicos puestos en el. El aparato parecía estar funcionando, así que Matias busco el fluido eléctrico y conectó la maquina.

Inmediantamente la maquina comenzó a funcionar dando unos sonidos extraños. Matias se percató que la maquina recogía un Ni objeto de metal con un valor numérico Ci escrito en el, de su bandeja procesadora. Mientras la maquina recogía una unidad de metal bloqueaba la entrada de otros objetos, de manera que no se podían sacar o meter más metales. Pero ¿El juego donde está? se pregunto Matias, el tambien observo que la maquina demoraba un tiempo Ti en mover un Ni objeto de su bandeja, mientras lo hacía el paso hacia la bandeja quebada descubierta, de manera que se podía sacar o meter cualquier otro objeto.

Matias encontro la manera de divertirse con este aparato mecácnico. Mientras la maquina se encontraba ocupada moviendo un Ni objeto metálico, Matias podía sacar otro Ni objeto de su bandeja, para sacar un objeto Matias necesita exactamente una unidad de tiempo. ¿Cuál será la cantidad mínima en la sumatoria de los Ci de los objetos que la maquina ha de mover, si Matias trata de sacar el máximo en la sumatoria Ci de los objetos que se encuentran en la bandeja?.

Recuerde, que Matias determina el orden en el que los elementos son cogidos por el aparato mecánico.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 ≤ M ≤ 100)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

La primera línea de entrada contiene el número N ( 1 ≤ N ≤ 2000 ).
En cada uno de los siguientes N líneas se describe por un par de números Ti, Ci ( 0 ≤ Ti ≤ 2000, 1 ≤ Ci < 10 ^ 9 ).
Si Ti es 0, Matias no será capaz de sacar nada, mientras que el aparato mecánico este ocupado con el objeto Ni.

Output

Salida. Un entero, la respuesta al problema: ¿cuál es el mínimo de los Ci que la maquina ha de mover?.

Entrada de ejemplo