Uno para muchos
El Uno es un juego de cartas muy popular. Las cartas tienen un número (entre 0 y 9) y un color (azul, amarillo, rojo o verde). Los jugadores empiezan con 7 cartas y tienen que irse deshaciendo de ellas colocándolas en el llamado pozo de descarte. Para poder colocar una carta en él, la anterior tiene que tener o bien el mismo número o bien el mismo color que aquella que se colocará encima. Hay además algunas cartas de acción que dan más variedad al juego.
Mariano Gana es muy aficionado a ese juego, sobre todo porque siempre se alza con la victoria contra su novia María. En unas semanas se van a ir a una casa rural con un montón de amigos y quiere llevárselo, pero como van a ser tantos le da miedo que el número de cartas se quede corto.
Está ideando un juego parecido donde las cartas tendrán solamente números, y no colores, pero en lugar de ser del 0 al 9 podrán tener muchos más dígitos. Para que una carta pueda colocarse encima de otra en el pozo de descarte basta con que ambas compartan al menos un dígito.
Está intentando equilibrar el juego para que no sea ni muy fácil ni muy difícil con la cantidad de gente que van a ser. Se está planteando un montón de posibles mazos de cartas y para cada uno querría saber cuántas parejas de cartas hay que puedan ponerse consecutivas en el pozo de descarte.
Entrada
La primera línea de la entrada contiene un único número con la cantidad de casos de prueba que vienen a continuación (no más de 5000).
Cada caso de prueba ocupa dos líneas. La primera indica cuántas cartas tiene el mazo candidato de Mariano (entre 1 y 300.000). La segunda línea contiene la lista de números de cada carta separados por un espacio. Los números pueden repetirse y no tendrán más de 9 dígitos. Además, Mariano ha decidido que nunca existirá la carta número 0.
Se garantiza que la suma del número de cartas de los mazos de los casos de prueba no superará 106.
Salida
Por cada caso de prueba el programa escribirá una línea con la cantidad de parejas de cartas que pueden ponerse juntas en el pozo de descarte.
Entrada de ejemplo
3 4 1 10 100 1000 4 10 2 31 1114 5 5 5 5 5 5
Salida de ejemplo
6 3 10