N queens are placed on a chessboard of size N × N. We'll say that these queens are in peaceful position if none of them can attack another. You are to find the total amount of peaceful positions that can be obtained from the given peaceful position by rearranging of exactly three queens.
The first line contains an integer N (4 ≤ N ≤ 50). It is followed by N lines describing positions of queens. Each line contains integers X and Y representing horizontal and vertical coordinates (1 ≤ X, Y ≤ N).
Output the number of peaceful positions that can be achieved from the initial position by moving of exactly three queens.
Note: the queens are not numbered so if you rearrange them on the chessboard using only squares they already occupied you’ll get the same peaceful position, not the new one.
Problem Author: Dmitry Filimonenkov
Problem Source: Ural Collegiate Programming Contest '99