ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1034. Queens in Peaceful Positions

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

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, YN).

Output

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.

Sample

inputoutput
4
2 1
1 3
3 4
4 2
0
Problem Author: Dmitry Filimonenkov
Problem Source: Ural Collegiate Programming Contest '99