| El mayor cuadrado please... |
Tomy tiene muchos cuadrados de paper. Las longitudes de los lados (los llamaremos simplemente "el tamaño") de estos cuadrados varía de 1 a N-1, y tiene una cantidad ilimitada de cada uno de estos tamaños. Un día, estando tan contento con sus cuadrados, se dio cuenta que lo que en realidad quería era un cuadrado de tamaño N. Aunque no lo tiene, puede construírselo con los otros cuadrados que tiene. Por ejemplo, un cuadrado de tamaño 7 puede construirse con 9 cuadrados menores, como se muestra abajo.
Notar que no debe haber ningún espacio vacío en el cuadrado, no debe haber papel extra fuera del cuadrado, y los cuadrados pequeños no se pueden solapar. Como puedes imaginarte, Tomy quiere conseguirlo usando el menor número de cuadrados posible.
La primera línea de la entrada contiene un único entero T, que indica el número de casos de prueba. Cada caso contiene un único entero N (2<=N<=50).
Para cada caso de prueba en la entrada, escribir una línea con un único entero K, indicando el mínimo número de cuadrados que se necesitan para constuir el cuadrado requerido. En las siguientes K líneas, cada una contiene tres enteros x,y,l, indicando las coordenadas de la esquina superior izquierda, y el tamaño del cuadrado correspondiente, respectivamente (con 1<=x,y<=N).