HDU多校1

赛中过了四题，代码能力真的捞，都是一眼思路然后敲大半个小时……

1011

题意：[0,1]随机生成n个数，然后m次操作，每次随机删除最小或最大的一个数，求最终剩下的数的和的期望。

思路：众所周知，期望这东西应用在随机数上，那就是他的平均值，即0.5。m次操作后剩下(n-m)个数，那么它的和的期望就是0.5*(n-m)，注意求下逆元即可。

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=1e9+7,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.x>v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

void solve(){
    scanf("%lld%lld",&n,&m);
    printf("%lld\n",(n-m)*two%mod);
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll t=1;
    scanf("%lld",&t);
    while(t--)solve();
}

1012

题意：n个数，每次操作Alice可以把这些数分成两个集合，然后Bob可以删掉任意一个集合，然后将剩下的集合内所有元素-1。如果集合中出现了0，那么Alice获胜，如果集合内没有元素，则Bob获胜。

（一开始脑子卡了，队友开出的）

思路：考虑如何能让Alice获胜：一个0就可以获胜，两个1的把1分在两边也可以获胜，4个2的话每边两个2，Bob删除一边后剩下一边-1，又变成了上一步的两个1…… 由此我们可以发现，如果i的数量≥2^i的话，Alice就可以一直平分，最终一定会变成0。同样，考虑一个例子，一个1两个2，Alice可以将其分成一边一个1，另一边两个2，我们发现不论Bob删掉哪边，Alice必赢。 由此可以总结出规律，两个2等价于一个1，同理，两个(i+1)可以等价于一个i。因此，只需要将所有＞0的数不停往小的数等价下来，最终判断是否会出现0，即可判断Alice的输赢。

1002

题意：给定n*m的一张地图，有墙有路，求从起点到终点最少需要删除几座墙。

思路：因为墙的数量只有15，所以枚举所有删墙的情况，然后每次bfs一遍即可。（一开始把删墙理解成跨墙，WA卡了好久）

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=40,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll b[M],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[M][M],mapp[M][M],flag;
struct qq{ll x0,y0,x1,y1;}q[M];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt,w,fg;}eg;

pair<ll,ll>pr[N];
vector<qq>v[N],vans;//v.assign(m,vector<ll>(n));
// priority_queue<qq,vector<qq>,cmps>sp;
queue<pair<ll,ll> >sq;
stack<ll>st;
map<ll,ll>mp;
set<ll>se,s0;
set<ll>::iterator it;
bitset<M>bi;

ll count(ll x){
    ll res=0;
    while(x){
        if(x%2)res++;
        x/=2;
    }
    return res;
}


void dfs(ll m){
    if(m==0){
        pr[++cnt]=mkp(count(key),key);
        return;
    }
    dfs(m-1);
    key^=b[m-1];
    dfs(m-1);
    key^=b[m-1];
}

void init(){
    key=0;cnt=0;
    ll p=1;
    L(i,0,15){
        b[i]=p;
        p*=2;
    }
    dfs(k);
    sort(pr+1,pr+cnt+1);
}

bool bfs(ll x0,ll y0,ll x1,ll y1){
    while(!sq.empty())sq.pop();
    vis[x0][y0]=1;
    sq.push(mkp(x0,y0));
    while(!sq.empty()){
        pair<ll,ll> tmp=sq.front();sq.pop();
        ll x=tmp.fi,y=tmp.se;
        vis[x][y]=1;
        if(x<0||y<0||x>n||y>m)continue;
        if(mapp[x][y])continue;
        if(x==x1&&y==y1)return 1;
        L(i,0,3){
            ll nx=x+dx[i],ny=y+dy[i];
            if(!vis[nx][ny]){
                vis[nx][ny]=1;
                sq.push(mkp(nx,ny));
            }
        }
    }
    return 0;
}

void solve(){
    ll x0,x1,y0,y1;
    scanf("%lld%lld%lld",&n,&m,&k);
    n*=2,m*=2;
    scanf("%lld%lld%lld%lld",&x0,&y0,&x1,&y1);
    x0=x0*2+1,x1=x1*2+1,y0=y0*2+1,y1=y1*2+1;
    init();
    L(i,0,k-1){
        scanf("%lld%lld%lld%lld",&x,&y,&l,&r);
        x*=2,y*=2,l*=2,r*=2;
        if(r<y)swap(r,y);
        if(l<x)swap(x,l);
        q[i]={x,y,l,r};
    }

    L(op,1,cnt){
        ll pp=pr[op].se;
        L(i,0,n)L(j,0,m){
            vis[i][j]=0,mapp[i][j]=0;
        }
        L(i,0,k-1){
            if(pp%2==0){
                x=q[i].x0,y=q[i].y0,l=q[i].x1,r=q[i].y1;
                if(x==l){
                    L(j,y,r)mapp[x][j]=1;
                }
                else{
                    L(j,x,l)mapp[j][y]=1;
                }
            }
            pp/=2;
        }
        //L(i,0,n){L(j,0,m)printf("%d",mapp[i][j]);printf("\n");}
        if(bfs(x0,y0,x1,y1)){
            ans=pr[op].fi;
            break;
        }
    }
    printf("%lld\n",ans);
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll t=1;
    scanf("%lld",&t);
    while(t--)solve();
}

1009

题意：棋盘中有n个点，判断是否存在一个点，使它朝8个方向射出的光线能包含所有点（米字形）。

思路：拿一个点出来枚举它被哪个方向的光线射到，然后再拿一个不在该光路上的点枚举它被哪个方向的光线射到，已知两条光路，然后求交点，判断即可，复杂度为O(43n)。

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=40,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll b[M],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[M][M],mapp[M][M],flag;
struct qq{ll x0,y0,x1,y1;}q[M];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt,w,fg;}eg;

pair<ll,ll>pr[N];
vector<qq>v[N],vans;//v.assign(m,vector<ll>(n));
// priority_queue<qq,vector<qq>,cmps>sp;
// queue<pair<ll,ll> >sq;
stack<ll>st;
map<ll,ll>mp;
set<ll>se,s0;
set<ll>::iterator it;
bitset<M>bi;

double eps=1e-5;
double sq(double x){return x*x;}
struct point{double x,y;}po[N],pox;
struct line{double A,B,C;}lin0,lin1;
line bd_line(point p,double a,double b){return {a,b,-a*p.x-b*p.y};}
point lin_inter(line l0,line l1){return {(l0.B*l1.C-l1.B*l0.C)/(l0.A*l1.B-l1.A*l0.B),(l0.C*l1.A-l1.C*l0.A)/(l0.A*l1.B-l1.A*l0.B)};}
double dis(point p,line k){return fabs(k.A*p.x+k.B*p.y+k.C)/sqrt(sq(k.A)+sq(k.B));}

bool judge(point px,point py){
    double x=px.x,y=px.y,nx=py.x,ny=py.y;
    if(fabs(y-ny)<=eps)return 1;
    if(fabs(x-nx)<=eps)return 1;
    if(fabs(y-ny-x+nx)<=eps)return 1;
    if(fabs(y-ny-nx+x)<=eps)return 1;
    return 0;
}

void solve(){
    scanf("%lld",&n);
    ans=0;
    L(i,1,n)scanf("%lf%lf",&po[i].x,&po[i].y);
    if(n<=2)ans=1;
    else{
        L(op1,1,4){
            p=n+1;
            if(op1==1)lin0=bd_line(po[1],0,1);
            else if(op1==2)lin0=bd_line(po[1],1,0);
            else if(op1==3)lin0=bd_line(po[1],1,1);
            else lin0=bd_line(po[1],1,-1);
            L(i,2,n){
                if(fabs(dis(po[i],lin0))>eps){
                    p=i;
                    break;
                }
            }
            if(p==n+1)ans=1;
            else{
                L(op2,1,4){
                    flag=1;
                    if(op1==op2)continue;
                    if(op2==1)lin1=bd_line(po[p],0,1);
                    else if(op2==2)lin1=bd_line(po[p],1,0);
                    else if(op2==3)lin1=bd_line(po[p],1,1);
                    else lin1=bd_line(po[p],1,-1);
                    pox=lin_inter(lin0,lin1);
                    L(i,p,n){
                        if(!judge(pox,po[i])){
                            flag=0;
                            break;
                        }
                    }
                    if(flag)ans=1;
                    // if(ans)printf("%lf %lf\n",pox.x,pox.y);
                    if(ans)break;
                }
            }
            if(ans)break;
        }
    }
    if(ans)printf("YES\n");
    else printf("NO\n");
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll t=1;
    scanf("%lld",&t);
    while(t--)solve();
}

1008

题意：给定n个点m条有向边，有边权，边分为普通边和特殊边，通过一条边的正常花费为这条边的边权。特殊的，假设通过特殊边到了点u，那么此时下一步可以去任意点v：如果点u到点v存在边，边权为w，那么此时通过该边的花费降低为(w-k)；假设点u到点v不存在边，那么此时花费为0。已知起点，求到每一个点的最小花费。

（一开场就先开了这题，由于读假，以为一眼最短路，直到写WA被拉去做签到，写完四题总算读对了，然后一直自闭WA到结束） 的 思路：考虑dijkstra最短路，将图分层，记录一个点由特殊边到的最小花费和非特殊边到的最小花费。我们可以发现如果一个点通过特殊边的能力（即花费为0）到达后，那么这个点的非特殊边到达的最小花费将不会再通过其他边到达了。即一个点通过原先不存在的边到达，最多只有一次。我们需要开set记录即可。其余按最短路标准。

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N][2],b[N],head[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt,w,fg;}eg[N*2];

bool cmp(qq u,qq v){
    return u.x<v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(qq u,qq v){
    return u.y>v.y;
}};//shun序

pair<ll,ll>pr;
vector<ll>vt,vans;//v.assign(m,vector<ll>(n));
priority_queue<qq,vector<qq>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
set<ll>se,s0;
set<ll>::iterator it;
bitset<M>bi;

void add(ll u,ll v,ll w,ll fg){
	eg[++cnt].to=v;
    eg[cnt].w=w;
    eg[cnt].fg=fg;
	eg[cnt].nxt=head[u];
	head[u]=cnt;
}

void solve(){
    scanf("%lld%lld%lld%lld",&n,&m,&p,&t);
    cnt=0;key=0;
    se.clear();
    L(i,1,n){
        head[i]=0,b[i]=0;
        a[i][0]=inf,a[i][1]=inf;
        if(p!=i)se.insert(i);
    }
    L(i,1,m){
        scanf("%lld%lld%lld%lld",&x,&y,&z,&pp);
        add(x,y,z,pp);
    }
    
    sp.push({p,0,0});    
    while(!sp.empty()){
        qq tmp=sp.top();sp.pop();
        ll x=tmp.x,w=tmp.y,op=tmp.z;
        if(a[x][op]<=w)continue;
        a[x][op]=w;//printf("%lld %lld %lld\n",x,op,w);

        if(!op)se.erase(x);
        key++;

        ll k=head[x];
        while(k){
            ll y=eg[k].to,dw=eg[k].w,fg=eg[k].fg;
            if(op)dw-=t,b[y]=key;
            if(a[y][fg]>w+dw)
                sp.push({y,w+dw,fg});

            k=eg[k].nxt;
        }
        if(op){
            vt.clear();
            for(auto y:se){
                if(b[y]!=key){
                    if(a[y][0]>w)sp.push({y,w,0});
                    vt.pb(y);
                }
            }
            ll siz=vt.size();
            L(i,0,siz-1){
                se.erase(vt[i]);
            }
        }
    }//printf("\n");
    L(i,1,n){
        ans=min(a[i][0],a[i][1]);
        if(ans==inf)printf("-1 ");
        else printf("%lld ",ans);
    }printf("\n");
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll t=1;
    scanf("%lld",&t);
    while(t--)solve();
}

1003

题意：常规背包，每个物品有体积和价值，求当恰好塞满背包的前提下，物品价值异或和的最大值。

思路：bitset优化，考虑O(n^3)的做法，dp[i][j][k]表示前i位异或和为j体积为k的是否能取到。我们发现，考虑体积为v，价值为w的物品时，dp[i][j][k]可以由dp[i-1][j^w][k-v]转移过来，我们只需配合bitset的左右移操作即可区间赋值。

#include<bits/stdc++.h>
#define ll int
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e5+10,M=1100,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool flag;
struct qq{ll x0,y0,x1,y1;}q[M];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt,w,fg;}eg;

pair<ll,ll>pr;
vector<qq>v,vans;//v.assign(m,vector<ll>(n));
// priority_queue<qq,vector<qq>,cmps>sp;
queue<pair<ll,ll> >sq;
stack<ll>st;
map<ll,ll>mp;
set<ll>se,s0;
set<ll>::iterator it;
bitset<M>bi[M],dp[M];

void solve(){
    scanf("%d%d",&n,&m);
    L(i,0,1023)dp[i].reset();
    dp[0][0]=1;
    L(i,1,n){
        scanf("%d%d",&x,&y);
        L(j,0,1023)bi[j]=dp[j^y]<<x;
        L(j,0,1023)dp[j]|=bi[j];
    }
    R(i,1023,0){
        if(dp[i][m]){
            printf("%d\n",i);
            return;
        }
    }
    printf("-1\n");
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll t=1;
    scanf("%d",&t);
    while(t--)solve();
}

1004

题意：有n个点在棋盘上，求一个三元组，满足三个点之间的距离的中位数是个质数。其中距离dis = (abs(x1 - x2) + abs(y1 - y2))。

思路：欧拉筛一遍质数。先n^2求出所有两点间距，然后按从小到大排序。遍历间距作为三边的中间值，假设此时间距所对应的两点为a,b，此时我们需要找到一个点c，满足dis(a,c)<=dis(a,b)&&dis(b,c)>=dis(a,b)（交换a,b也是一样的），因此我们能只需记录在此之前，我们有哪些点的间距已经被遍历过了。举个栗子，当前边是(a,b)，边(a,c)之前已经被记录了，而边(b,c)没被记录过，那么点(a,b,c)就是一个满足条件的三元组。放在bitset中，即bi[a][c]^bi[b][c]==1，(a,b,c)就是一个满足条件的三元组。

#include<bits/stdc++.h>
#define ll int
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=4e6+10,M=2010,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[M],b[M],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool flag;
struct qq{ll x,y,z;}q[N];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt,w,fg;}eg;

bool cmp(qq u,qq v){
    return u.z<v.z;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<qq>v,vans;//v.assign(m,vector<ll>(n));
// priority_queue<qq,vector<qq>,cmps>sp;
queue<pair<ll,ll> >sq;
stack<ll>st;
map<ll,ll>mp;
set<ll>se,s0;
set<ll>::iterator it;
bitset<M>bi[M];

bool visprime[N];
ll prime[N];
void oulasai(ll n){
    cnt=0;
    visprime[1]=1;
    L(i,2,n){
        if(!visprime[i])prime[++cnt]=i;
        L(j,1,cnt){
            if(i*prime[j]>n) break;
            visprime[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

void solve(){
    scanf("%d%d",&n,&t);
    L(i,0,n)bi[i].reset();
    m=0;ans=0;
    L(i,1,n){
        scanf("%d%d",&a[i],&b[i]);
        L(j,1,i-1){
            q[++m]={i,j,abs(a[i]-a[j])+abs(b[i]-b[j])};
        }
    }
    sort(q+1,q+m+1,cmp);
    L(i,1,m){
        ll x=q[i].x,y=q[i].y,z=q[i].z;//printf("%d ",z);
        if(!visprime[z]){
            ans+=(bi[x]^bi[y]).count();
        }
        bi[x][y]=1;
        bi[y][x]=1;
    }
    printf("%d\n",ans);
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    oulasai(200000);
    ll t=1;
    scanf("%d",&t);
    while(t--)solve();
}