DNI incompleto
En España, el Documento Nacional de Identidad (DNI) es un documento público, personal e intransferible, emitido por el Ministerio del Interior, que acredita la identidad y los datos personales de su titular, así como la nacionalidad española del mismo.
El DNI contiene un número personal de 8 dígitos, único, correspondiente al Número de Identificación Fiscal (NIF), y un carácter de verificación compuesto por una letra mayúscula. Para verificar el NIF, el algoritmo de cálculo del carácter de control es el siguiente: se divide el número entre 23 y el resto se utiliza para determinar la letra según la siguiente tabla:
| Resto | Letra | Resto | Letra | Resto | Letra | ||
| 0 | T | 8 | P | 15 | S | ||
| 1 | R | 9 | D | 16 | Q | ||
| 2 | W | 10 | X | 17 | V | ||
| 3 | A | 11 | B | 18 | H | ||
| 4 | G | 12 | N | 19 | L | ||
| 5 | M | 13 | J | 20 | C | ||
| 6 | Y | 14 | Z | 21 | K | ||
| 7 | F | 22 | E |
Por ejemplo, si el número de identificación fiscal es 12345678, dividido entre 23 da resto 14, por lo que la letra sería la Z y el número del DNI completo sería 12345678Z.
Pues bien, nos ha llegado un DNI escaneado donde su número aparece algo borroso y hay varios dígitos ilegibles. Queremos saber cuántos números de DNI válidos son compatibles con la información que sí tenemos, a ver si tenemos suerte y son pocos. Por ejemplo, si el número que vemos es 1234567?Z, donde hemos utilizado el símbolo ? para representar el dígito ilegible, sabemos que corresponde a un único número válido, ya que sustituir la ? por cualquier otro dígito que no sea el 8, daría un carácter de control que no sería la Z.
Entrada
La entrada comienza por un número N que indica el número de DNIs que aparecerán a continuación, cada uno en una línea.
Todos los DNIs están formados por nueve caracteres. Los ocho primeros serán dígitos entre 0 y 9 o el símbolo ? que indica que ese dígito es ilegible. Habrá de 1 a 4 dígitos ilegibles. El noveno carácter será una letra mayúscula.
Se garantiza que el número recibido, aun con dígitos ilegibles, corresponde a un DNI válido.
Salida
Para cada número de DNI recibido, se escribirá el número total de posibles DNIs que son compatibles con él.
Entrada de ejemplo
3 1234567?Z 012??567L ?87?54?2M
Salida de ejemplo
1 4 43