reines

Le problème des reines est un problème classique, il s'agit de placer n reines sur un échiquier de n par n cases, de manière à ce qu'aucune reine ne soit dans le couloir de déplacement d'une autre reine. Pour rappel, les reines se déplacent horizontalement, verticalement et en diagonale d'un nombre quelconque de cases. Il est donc impossible d'en placer n+1 sur un échiquier de taille n par n.

On s'intéresse à une variante du problème ou certaines cases sont interdites (mais une reine peut la traverser lors d'un déplacement). Chaque testcase commence par l'entier n (n étant compris au sens large entre 1 et 13) qui représente la taille de l'échiquier et le nombre de reines à placer. Il y a ensuite n lignes de n caractères qui représentent l'échiquier, les cases "." sont les cases libres et les cases "*" représentent les cases interdites. Pour chaque testcase vous devez calculer le nombre de manière de placer les n reines en respectant toutes les contraintes. Deux configurations identiques à symétrie ou rotation près sont considérées différentes.

Input

8
........
........
........
........
........
........
........
........
4
.*..
....
....
....
4
**.*
.***
***.
*.**

Télécharger l'entrée

Output

92
1
1

Télécharger la sortie

Il faut être logué pour pouvoir envoyer une soumission.