A point set P is (a, b)-L if and only if there exists x, y satisfying:
P = {(x, y), (x + 1, y), . . . , (x + a, y), (x, y + 1), . . . , (x, y + b)}(a, b ≥ 1)
A point set Q is good if and only if Q is an (a, b)-L set and gcd(a, b) = 1.
Matt is given a point set S. Please help him find the number of ordered pairs of sets (A, B) such that:
For each test case, the first line contains an integer N (0 ≤ N ≤ 40000), indicating the size of the point set S.
Each of the following N lines contains two integers xi, yi, indicating the i-th point in S (1 ≤ xi, yi ≤ 200). It’s guaranteed that all (xi, yi) would be distinct.
n the second sample, the ordered pairs of sets Matt can choose are:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=;
const int M=;
int R[M][M],U[M][M];
bool mp[M][M];
int dp[M][M],cnt[M][M];
int t[M][M]; int gcd(int a,int b) { return (b==)?a:gcd(b,a%b); } void init()
{
for(int i=;i<M;i++)
for(int j=;j<M;j++)
{
dp[i][j]=dp[i][j-]+((gcd(i,j)==)?:);
cnt[i][j]=cnt[i-][j]+dp[i][j];
}
}
int main()
{
init();
int T,Case=;
cin>>T;
while(T--)
{
int n; scanf("%d",&n);
memset(mp,,sizeof(mp));
memset(U,,sizeof(U));
memset(R,,sizeof(R));
memset(t,,sizeof(t));
for(int i=;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
mp[x][y]=;
}
for(int i=;i>=;i--)
{
for(int j=;j>=;j--)
{
if(mp[i][j]){
if(mp[i+][j]) U[i][j]=U[i+][j]+;
if(mp[i][j+]) R[i][j]=R[i][j+]+;
}
}
}
LL s=;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if(mp[i][j]){
s+=cnt[U[i][j]][R[i][j]];
int d=;
for(int k=U[i][j];k>=;k--)
{
d+=dp[k][R[i][j]];
t[i+k][j]+=d;
}
}
}
}
LL ans=;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if(mp[i][j]){
LL p=t[i][j];
LL pp=cnt[U[i][j]][R[i][j]];
p-=pp;
for(int k=;k<=R[i][j];k++)
{
p+=t[i][j+k];
ans+=*p*dp[k][U[i][j]];
}
ans+=pp*pp;
}
}
}
s=s*s-ans;
printf("Case #%d: %lld\n",Case++,s);
}
return ;
}