#include using namespace std; #if __has_include() #include using namespace atcoder; templateistream &operator>>(istream &is,static_modint &a){long long b;is>>b;a=b;return is;} istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} #endif #ifdef LOCAL #include "debug.h" #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) #define esper(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<(0) ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } void SOLVE(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout<>testcase; for(int i=0;i vectorcartesian_tree(vector&a){ int n=a.size(); if constexpr(!MIN){ rep(i,n)a[i]*=-1; } vectorret(n,-1); stackst; rep(i,n){ int ls=-1; while(!st.empty()){ int x=st.top(); if(a[x]>=a[i]){ ls=x; st.pop(); } else break; } if(ls!=-1)ret[ls]=i; if(!st.empty())ret[i]=st.top(); st.push(i); } return ret; } void SOLVE(){ int h,w,n; cin>>h>>w>>n; vectors(h,string(w,'.')); rep(i,n){ int a,b; cin>>a>>b; a--,b--; s[a][b]='#'; } ll ans=0; vectordp(w,0); for(int i=h-1;i>=0;i--){ rep(j,w){ if(s[i][j]=='#')dp[j]=0; else dp[j]++; } auto c=cartesian_tree(dp); vectorleft(w,-1),right(w,-1); int root=-1; rep(j,w){ if(c[j]==-1)root=j; else (jvoid { ans+=ll(dp[x])*(x-l+1)*(r-(x+1)+1); if(left[x]!=-1)self(self,left[x],l,x); if(right[x]!=-1)self(self,right[x],x+1,r); }; dfs(dfs,root,0,w); } cout<