// warm heart, wagging tail,and a smile just for you!
//                         _ _ _ __ __ __  __ _ _ __ _ _ __ _ __ ____ _ _ _ _ _ _ _ _ 
//                          ||__|| || ||\\//||  //__\\  ||\\ || ||__   ||__||  ||  ||
//                          ||  || || ||    || //    \\ || \\||  ___|| ||  ||  \\__//
//                                                    _ ___ _ _ _ _  _ __ _ _ __ _ __ _ __ _ _ __ ___ __ _ _ _ _ ___ _ _ ___
//                                                    ||__   ||__||  //__\\  ||\\ || ||// ||__|| ||  ]] ||__||  //__\\  ||__))
//                                                    ____|| ||  || //    \\ || \\|| ||\\ ||  || ||__]] ||  || //    \\ || \\
//                                                                     ¦¦¦¦¦¦¦¦¦¦¦
//                                                                   ¦¦¦++++++++++¦¦¦
//                                                                ¦¦¦+++++¦¦¦¦++++++¦¦¦
//                                            ¦¦¦¦¦¦¦¦¦¦¦       ¦¦+++++¦¦¦¦++¦¦¦¦+++++¦¦
//                                      ¦¦¦¦¦¦¦¦¦+++++¦¦¦¦¦¦¦¦¦¦¦¦+++++¦¦++++++¦¦¦+++++¦¦
//                               ¦¦¦¦¦¦¦¦++++++++++++++++++++++¦¦¦¦¦¦¦¦¦++++++¦¦+++++++¦¦
//                             ¦¦¦¦+¦¦+++++++++++++++++++++++++++++¦¦¦¦¦¦¦¦¦+++++++++++¦¦                 
//                           ¦¦¦+++¦++++++++++++++++++++++++++++++++++++¦¦++¦¦¦+++++++¦¦¦¦¦                                        
//                         ¦¦¦+++++++++++++++++++++++++++++++++++++++++++¦¦+++¦¦¦¦¦¦¦¦+++++¦¦                             
//                       ¦¦¦++++++++++++++++++++++++++++++++++++++++++++++++++++¦¦¦+++++++++¦¦¦              
//                     ¦¦¦++++++++++++++++++++++++++++++++++++++++++++++++++++++++¦¦¦¦¦+++++++¦¦             
//                 ¦¦¦¦++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++¦¦¦¦+++++¦¦¦¦
//     ¦¦¦¦¦¦¦¦¦¦¦¦¦++++++++¦¦+++++¦¦¦¦+++++++++++++++++¦¦¦¦¦+++++++++++++++++++++++++++¦¦¦++++¦¦¦¦¦¦            
//   ¦¦¦¦+++++++++++++++++++¦¦++¦¦¦¦¦¦+++++++++++++++++++++¦¦¦¦¦¦+++++++¦¦¦¦¦¦¦¦¦¦¦++++++++¦¦+++¦¦+++¦¦
// ¦¦¦++++++++++++++++++++¦¦+++++++++++++++++¦¦+++++++++++++++++++++¦¦¦¦+++++++++++¦+++++++¦¦++++++++¦¦
// ¦¦+++++++++++++++++++++¦¦++++¦¦¦¦¦¦+++¦¦¦¦++¦¦¦¦+++++++¦¦¦¦¦¦¦¦¦¦+++++++++++++++++++++++¦¦+++++++¦¦¦
// ¦¦+++++++++++++++++++++¦¦¦¦¦¦¦¦¦¦¦¦¦+++++++++++++++++++¦¦¦¦¦¦¦¦¦++++++++++++++++++++++++¦¦++++¦¦¦¦¦
// ¦¦¦++++++++++++++++++¦¦¦+++++¦¦++++++++++++++++++++++++++++¦¦¦¦¦++++++++++++++++++++++++¦¦¦¦¦¦¦¦
//   ¦¦¦+++++++++++++¦¦¦¦¦++++++++¦¦++++++++++++++++++++++++¦¦¦++¦¦+++++++++++++++++++++++¦¦
//       ¦¦¦¦¦¦¦¦¦¦¦¦¦¦  ¦¦¦¦++++++¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦+++++¦¦+++++++++++++++++++¦¦¦¦
//                         ¦¦¦¦¦¦¦                           ¦¦¦¦¦  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
//
//#include<boost/multiprecision/cpp_int.hpp>
#include <bits/stdc++.h>
const long double pi = 3.1415926535897932384626433832795;
#define scn(n) scanf("%d",&n)

#define lscn(n) scanf("%lld ",&n)

#define scn2(n1,n2) scanf("%d%d",&n1,&n2)

#define lscn2(n1,n2) scanf("%lld%lld",&n1,&n2)

#define lpri(n) printf("%lld ",n)

#define lpri2(n1,n2) printf("%lld %lld\n",n1,n2)

#define pri(n) printf("%d ",n)

#define pri2(n1,n2) printf("%d %d\n",n1,n2)

#define pln() printf("\n")

#define priln(n) printf("%d\n",n)

#define lpriln(n) printf("%lld\n",n)

#define RAL(i,x,n) for(int i=x;i<n;i++)

#define RALR(i,x,n) for(int i=x-1;i>=n;i--)
//insert function in vector is used to insert a value at given index
//ex: v.insert(v.begin(),10); inserts 10 at 0th position in vector 

//vector.resize(3) is used to resize the size of given array 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define mp make_pair

#define F first

#define S second
#define sq(a) (a)*(a)
#include<unordered_set>
#define lli long long int
#define toh_shuru_karte_hai_bina_kise_bakchodi_ke ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define test lli t;cin>>t;while(t--)
#define arrin lli n;cin>>n;lli a[n];for(lli i=0;i<n;i++)cin>>a[i]       // a%b=a-b*floor(a/b);
#define floop for(lli i=0;i<n;i++)
#define mod 1000000007
#define defvec vector<lli>v
#define ub upper_bound
#define pb push_back
#define pob pop_back
#define mp make_pair
#define emp emplace_back
#define bs binary_search
#define pi 3.1415926536
#define INF ll(8230219982008199610)
#define MINF ll(-8230219982008199610)
#define ones(n) __builtin_popcountll(n)
#define focc(n) __builtin_ffsll(n) //to count index of first 1 from right in binary representation of a number starting from index 1
#define leadingzero(n) __builtin_clzll(n)
#define trailingzeroes(n) __builtin_ctzll(n)
#define loop0(i,n) for(int i=0; i<n; i++)
#define loop1(i,n) for(int i=1; i<=n; i++)
#define rev0(i,n)  for(int i=n-1; i>=0; i--)
#define rev1(i,n)  for(int i=n; i>0; i--)
#define code lli n,k;cin>>n>>k;lli a[n];loop0(i,n) cin>>a[i]
#define loopj(j,k,n) for(lli j=k;j<n;j++)
#define all(x) x.begin(), x.end()
#define print(v) for(auto x:v)cout<<x<<" "
#define prints for(lli i=0;s[i];i++)cout<<s[i]
//using namespace boost::multiprecision ;
//typedef long long ll;
//typedef vector<lli> vi;
//typedef pair<lli,lli> pi;
using namespace std;

//atoll(s.c_str())  to convert string s into long long int
//all_of(a,a+n,ispositive());  //to check all the elements in array are positive
//any_of(a,a+n,ispositive());  //to check any element in array is positive
//none_of(a,a+n,ispositive());  //to check none of the elements in array is positive
//copy_n(a,n,b);  //to copy all the elements from a to b
//iota(a,a+n,10); //this will print consequtive n terms starting from 10 //ex if n=5 than 10,11,12,13,14
//same can be used for character array

//a number is divisible by 8 if last three digits of it is divisible by 8
//ex. 1512 as 512 is divisible by 8 so 1512 is also divisible by 8

/* NUMBER OF WAYS TO PLACE TWO QUEENS ON A BOARD OF SIZE n*n SUCH THAT THEY DO NOT ATTACK ON EACH OTHER
   count=(pow(n,4)/2)-(5*(pow(n,3)/3)+(3*pow(n,2)/2)-n/3;
*/
/* bitset<10>s;
  s[0]=1;
  s[3]=1;
  s[5]=1;
  s[7]=1;
  cout<<s;
 output is 1001010100
  cout<<s.count();
  output is frequency of 1 so 4

*/

// a number is power of 4 if num>0 && log2(num)/2==(int)log2(num)/2

#define INT_BITS 16
//if(abs(a-b)<1e-9)                  //TO COMPARE FLOATING POINT INTEGER
//{  
//    a and b are equal
//}

//string s=R"(HIMANS&\nSHAN\t)"; we can print a whole string same as given by doing this
//vector<int>v={1,2,3,4};
//vector<int>w=move(v);
//after this v={};
//w={1,2,3,4};
// to reverse a string reverse(str.begin(), str.end());
//  OR
// string rev = string(str.rbegin(),str.rend());

//q.front() operation works in queue but not works in priority_queue
//so for priority_queue q.top() is used
// ~x=-(x+1)  ex: ~29=-30;

unsigned lli leftRotate(unsigned lli n, unsigned lli d) 
{ 
    return (n << d)|(n >> (INT_BITS - d)); 
} 
unsigned lli rightRotate(unsigned lli n,unsigned lli d) 
{ 
    return (n >> d)|(n << (INT_BITS - d)); 
} 
//TO SET Kth BIT AS ONE n|(1<<k) while n&(~(1<<k)) sets the kth bit of n to 0
//and n^(1<<k) inverts the kth bit of n
//The number of digits of an integer x in base b can be calculated using the formula
//[logb(x) + 1]. For example, [log3(17) + 1] = 3.
//Every composite number has at least one prime factor less than or equal to square root of itself
int log2(int x)
{
  int res=0;
  while(x>>=1)
  res++;
  return res;
}
lli comb(lli n,lli r)

{
    
if(r==0||r==n)
           //VALUE OF nCr
return 1;
    
return 
comb(n-1,r)+comb(n-1,r-1);

}
bool isPowerOfTwo(int n) 
{ 
   if(n==0) 
   return false; 
  
   return (ceil(log2(n)) == floor(log2(n))); 
} 
lli inverse(lli a,lli m)
{
    return 1<a?m-inverse(m%a,a)*(m/a):1;    //for fastly calculate inverse modulo
}
lli issorted(lli arr[], lli n) 

{ 
 if (n == 1 || n == 0) 
        
return 1; 
  
 
if(arr[n - 1] < arr[n - 2]) 
       
return 0; 
  


return issorted(arr, n - 1); 

} 

int computeXOR(int n)
{
  if(n%4==0)
  return n;                        //TO CALCULATE XOR FROM 1 TO N
  if(n%4==1)
  return 1;
  if(n%4==2)
  return n+1;
  else
  return 0;
}

lli count(string s)//count distinct element in string
{
    lli ans=1,i,j;
    for(i=1;i<s.length();i++)
    {
        for(j=0;j<i;j++)
        {
            if(s[i]==s[j])
            break;
        }
        if(i==j)
        ans++;
    }
    return ans;
}

bool isPerfectSquare(long double x) 

{   
  // Find floating point value of  
  
// square root of x. 
  
long double sr = sqrt(x); 
  
  
// If square root is an integer 
  
return ((sr - floor(sr)) == 0); 

} 

lli countarray(lli a[],lli n)//count distinct element in array
{
  unordered_set<lli>s;
for(lli i=0;i<n;i++)
s.insert(a[i]);
return s.size();
}



bool check (int N)          //to check whether ith bit of n is 1 or 0
    {  lli i;
        if( N & (1 << i) )
            return true;
        else
            return false;
    }



bool isvowel(char ch)      
{
    string s = "aeiouAEIOU";
    for (char c : s)
    {
        if (c == ch)
        {
            return true;
        }
    }
    return false;
}



bool isPrime(lli n) 
{ 
    if(n<=1)  return false; 
    if(n<=3)  return true; 
    if(n%2==0||n%3==0) return false; 
    for(lli i=5; i*i<=n; i=i+6) 
    if (n%i == 0 || n%(i+2) == 0) 
    return false; 
    return true; 
}



struct interval

{
    int start,end;
   
 
};
                                             //SORTING IN A SPECIAL ORDER
bool compare(interval x,interval y)

{
    return (x.start<y.start);
}


bool isSubstring(string s1, string s2) 
{ 
    int M = s1.length(); 
    int N = s2.length(); 
  
    /* A loop to slide pat[] one by one */
    for (int i = 0; i <= N - M; i++) { 
        int j; 
  
        /* For current index i, check for 
 pattern match */
        for (j = 0; j < M; j++) 
            if (s2[i + j] != s1[j]) 
                break; 
  
        if (j == M) 
            return true; 
    } 
  
    return false; 
} 

int count_primes_in_range(int n)  //to count number of primes from 1 to n
{
   
bool isprime[n+1];
    
for(int i=2;i<=n;i++)
    
isprime[i]=true;
    
isprime[0]=false;
    
isprime[1]=false;
    
for(int i=2;i<=sqrt(n);i++)
    
{   
if(isprime[i]==true)
       
{
           
for(int j=i*i;j<=n;j+=i)
        
{
           
isprime[j]=false;
               
}

}
      
    
}
    
int count=0;
    
for(int i=0;i<=n;i++)
    
{
        
if(isprime[i]==true)
        
count++;
    
}
    
return count;

}



void multiply(int a[2][2],int m[2][2])

{                                                 //
int him[2][2];
                                    //   MATRIX EXPONENTIATION
for(int i=0;i<2;i++)
                              //
{   
                                              //
for(int j=0;j<2;j++)
        
{   him[i][j]=0;
            
for(int k=0;k<2;k++)
            
{
                
him[i][j]+=(a[i][k]*m[k][j]);
            
}
            
        
}
    
}
    
for(int i=0;i<2;i++)
    
{
        for(int j=0;j<2;j++)
        
{
            a[i][j]=him[i][j];
        
}
    
}
}
void power(int a[2][2],int n)

{   if(n==0||n==1)
    
return;
    
power(a,n/2);
    
multiply(a,a);
    
if(n%2!=0)
    
{  
int m[2][2]={{1,1},{1,0}};
        
multiply(a,m);
    
}

}
int fib(int n)

{
    
int a[2][2]={{1,1},{1,0}};
    
if(n==0)
    
return 0;
    
power(a,n-1);
    
return a[0][0];

}




lli power_(lli a,lli n) 
{ 
    lli res = 1;      
   
    while (n > 0) 
    { 
        if (n& 1) 
            res = ((res)*(a)); 
        n/=2; 
        a=((a)*(a));
    } 
    return res; 
}
int factmod(int n, int p) {
    vector<int> f(p);
    f[0] = 1;
    for (int i = 1; i < p; i++)
        f[i] = f[i-1] * i % p;

    int res = 1;
    while (n > 1) {
        if ((n/p) % 2)
            res = p - res;
        res = res * f[n%p] % p;
        n /= p;
    }
    return res; 
}

lli modularexponentiation(lli a,lli n,lli mo) 
{ 
    lli res = 1;      
   
    while (n > 0) 
    { 
        if (n& 1) 
            res = ((res%mo)*(a%mo))%mo; 
        n/=2; 
        a=((a%mo)*(a%mo))%mo;
    } 
    return res; 
}



lli largest_power(lli N)
    {                                              //LARGEST POWER OF 2 JUST LESS THAN OR EQUAL TO A GIVEN 16 BIT NUMBER
        //changing all right side bits to 1.
        N = N| (N>>1);
        N = N| (N>>2);
        N = N| (N>>4);
        N = N| (N>>8);
        N = N| (N>>16);  

    //as now the number is 2 * x-1, where x is required answer, so adding 1 and dividing it by
                return (N+1)>>1;

    }

bool alternate(lli n)
{
    lli i;
    if((n^(n>>1))==(pow(2,i)-1))           //this is to check that in binary representation of n, n has alternate sequence or not
    return true;                             //ex.101010          if n^(n>>1) is like this 11111 or containing only set bits than yes otherwise no  
return false;
}

    lli countDivisors(lli n) 
{ 
    lli cnt = 0; 
    for (int i = 1; i <= sqrt(n); i++) { 
        if (n % i == 0) { 
            // If divisors are equal, 
            // count only one 
            if (n / i == i) 
                cnt++; 
  
            else // Otherwise count both 
                cnt = cnt + 2; 
        } 
    } 
    return cnt;
}


int highestpowerof2(int n)   //highest power of 2 which divides a given number
{
    return (n&(~(n-1)));
}

/*lli dectobin(lli n)
{                                           //DECIMAL TO BINARY FOR A 32 BIT INTEGER
for (int i = 31; i >= 0; i--) {
if (n&(1<<i)) cout << "1";
else cout << "0";
}
}*/
/*lli maxfrequency(lli v[],lli n)
{    lli n;
		cin >> n;
                lli a[n];
		vector<lli> cnt(n + 1);
		for (int i = 0; i < n; ++i) {
			cin>>a[i];
			++cnt[a[i]];
		}
		lli mx = *max_element(cnt.begin(), cnt.end());
		lli diff = n + 1 - count(cnt.begin(), cnt.end(), 0);//COUNT OF DIFFERENT ELEMENTS PRESENT IN ARRAY
return mx;
}*/
void lowertoupper(char ch)
{
   ch=ch&'_';
  cout<<ch<<" ";
}
void uppertolower(char ch)
{
  ch=ch|' ';
  cout<<ch<<" ";
}
lli primecounter(lli l,lli r)
{                              //this counts prime in range l to r both inclusive
   lli fact=1,count=0;
   for(lli i=l;i<=r;i++)
   {
      if(((fact-i)%((1LL<<i)-1))==0)
      count++;
    fact*=((1LL<<i)-1);
   }
  return count;
} 
lli counteprime(lli l,lli r)
{
   lli count=0,i,j;
  for(i=l;i<=r;i++)           //THIS WILL ALSO GIVE COUNT OF PRIMES IN RANGE L TO R
  {
     for(j=2;j<=(i/j);j++)
     {
       if(!(i%j))
       break;
     }
      if(j>(i/j))
      count++;
   }
return count;
}
void pairsort(int a[], char b[], int n)     //SORT AN ARRAY ACCORDING TO SECOND ARRAY
{ 
    pair<int, char> pairt[n]; 
  
    // Storing the respective array 
    // elements in pairs. 
    for (int i = 0; i < n; i++)  
    { 
        pairt[i].first = a[i]; 
        pairt[i].second = b[i]; 
    } 
  
    // Sorting the pair array. 
    sort(pairt, pairt + n); 
      
    // Modifying original arrays 
    for (int i = 0; i < n; i++)  
    { 
        a[i] = pairt[i].first; 
        b[i] = pairt[i].second; 
    } 
} 
lli fibo(lli n)
{
    long double him=(1+sqrt(5))/2;
  return round(pow(him,n)/sqrt(5));
}
lli binToDec(string c) 
{  
    lli count=0;
    for(lli i=0;i<c.length();i++)
   {
       if (c[i] == '1'){
            lli val = 1;
           for(lli j=0;j<i;j++)
           {
                val *= 2;
            }
            count += val;
        }
   }
   return count;
} 
void rev(int a[],int n)
{
        for(lli i=0,j=n-1;i<j;i++,j--)
        {
            swap(a[i],a[j]);
        }
        loop0(i,n)
        cout<<a[i]<<" ";
}
/*void concatenate(int arr1[], int arr2[], int m, int n) 
{ 
   memcpy(arr1 + m, arr2, sizeof(arr2));    //TO CONCATENATE TWO ARRAYS
} */
vector<lli> Eratosthenes(int n) 
{
    vector<lli> res;
    vector<bool> Prime(n + 1, true);
    Prime[0] = Prime[1] = false;
    for(int i=4;i<=n;i+=2)
    {
        Prime[i]=false;
    }
    for (int i = 3; i * i <= n; i+=2) 
    {
        if (Prime[i]) 
        {
            for (int j = i*i; j <= n; j+=i) 
            {
                if(Prime[j]==true)
                Prime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++) 
    {
        if (Prime[i]) 
        {
            res.emplace_back(i);
        }
    }
    return res;
}
bool isvalid(lli x,lli y,lli n,lli m)
{
    if(x<0||x>(n-1)||y<0||y>(m-1))
    return false;
    //if(visited[x][y]==true)
    //return false;
    return true;
}
lli bs(lli a[],lli start,lli end,lli x,lli n)
{
    lli mid=start+(end-start)/2;
    if(start>end)
    return -1;
    if(a[mid]==x)
    return mid;
    else if(a[mid]>x)
    return bs(a,start,mid-1,x,n);
    else 
    return bs(a,mid+1,end,x,n);
}
void transpose(vector<vector<lli>>&v)
{
    loop0(i,v.size())
    {
        loop0(j,i)
        {
            swap(v[i][j],v[j][i]);
        }
    }
}
map<lli,lli> primeFactors(lli n)  
{  
    map<lli,lli>mp;
    while (n % 2 == 0)                          //PRIME FACTORISATION IN SQRT(n)
    {  
        mp[2]++;
        n=n/2;
    }  
    for (lli i = 3; i <= sqrt(n); i = i + 2)  
    {  
        while (n % i == 0)  
        {  
           mp[i]++;                 //PRIME FACTORIZATION
            n = n/i;  
        }  
    }  
    if (n > 2)  
        mp[n]++;
        /*for(auto x:mp)
        {
            cout<<x.first<<" "<<x.second<<endl;
        }*/
        return mp;
}  
void primefactors(lli n)
{                                     //PRIME FACTORISATION USING SIEVE
    lli d[n+1];
    memset(d,-1,sizeof(d));
    d[1]=1;
    for(lli i=2;i<=n;i+=2)
    {
        d[i]=i;
    }
    for(lli i=3;i<=n;i+=2)
    {
        if(d[i]==-1)
        {
            for(lli j=i;j<=n;j+=i)
            {
                if(d[j]==-1)
                {
                    d[j]=i;
                }
            }
        }
    }
    
    // for(lli i=1;i<=n;i++)
    // cout<<d[i]<<" ";
    map<lli,lli>mp;
    while(n>1)
    {
        mp[d[n]]++;
        n=n/d[n];
    }
   // for(auto x:mp)
    //cout<<x.first<<" "<<x.second<<endl;
}
lli gcd (lli a, lli b) {
    return b ? gcd (b, a % b) : a;
}
lli lcm (lli a,lli b) {
    return a / gcd(a, b) * b;
}
lli SubArraySum(lli arr[] ,lli n ) 
{ 
    lli result = 0; 
    for (lli i=0; i<n; i++) 
        result += (arr[i] * (i+1) * (n-i)); 
    return result ; 
} 
lli countsetbits(lli n)
{
    lli count=0;
    while(n)
    {
        count++;
        n=n&(n-1);
    }
    return count;
}
lli nCr(lli n,lli k) 
{
    double res = 1;
    for (lli i = 1; i <= k; ++i)
        res = res * (n - k + i) / i;
    return (int)(res + 0.01);
}
lli gcd_(lli a,lli b) 
{
    if (!a || !b)      //if a==0 || b==0 than simply return other element
        return a | b;
    unsigned shift = __builtin_ctzll(a | b);  //this will count min 2 factor in both numbers
    a >>= __builtin_ctzll(a);
    do {
        b >>= __builtin_ctzll(b);
        if (a > b)
            swap(a, b);
        b -= a;
    } while (b);
    //finally b will become 0 and a will contain our result
    return a << shift;
}
pair<lli,lli> fib (lli n) {
    if (n == 0)
        return {0ll, 1ll};
                                                             //FIBONACCI IN logN
    auto p = fib(n >> 1ll);
    lli c = ((p.first%mod)*((2 * (p.second%mod))%mod - (p.first%mod)+mod)%mod)%mod;
    c=c%mod;
    lli d =((((p.first%mod) * (p.first%mod))%mod) + ((p.second%mod) * (p.second%mod))%mod)%mod;
    d=d%mod;
    lli x=(c+d)%mod;
    if (n%2!=0)
        return {d,x};
    else
        return {c, d};
}
lli nCrModPFermat(lli n, lli r)
{
    if (n < r)
        return 0;
    if (r == 0)
        return 1;
    lli fac[n + 1];
    fac[0] = 1;
    for (lli i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % mod;
 
    lli ans=((fac[n] %mod)* modularexponentiation(fac[r],mod-2,mod)) % mod;
    ans=(ans*modularexponentiation(fac[n - r], mod-2,mod)) % mod;
    return ans;
}
lli calc(lli a[],lli b[],lli n,lli x,lli y)
{
    lli sum=0;
    loop0(i,n)
    {
        sum+=abs(a[i]-x)+abs(b[i]-y);
    }
    return sum;
}
int main()
{
   toh_shuru_karte_hai_bina_kise_bakchodi_ke;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
test{
   lli n;
   cin>>n;
   lli a[n],b[n];
   loop0(i,n)
   cin>>a[i]>>b[i];
   vector<pair<lli,lli>>v;
   loop0(i,n)
   v.pb({a[i],b[i]});
		if(n==1)
		{
			cout<<1<<endl;
		}
		else
		{
		    if(n==2)
		    {
		        if((v[0].first == v[1].first) || (v[0].second == v[1].second))
		     {
		         lli ans=abs(v[0].first-v[1].first)+abs(v[0].second-v[1].second)+1;
			cout<<ans<<endl;
		    }
		    else
		    {
		      sort(a,a+n);
		   sort(b,b+n);
		   lli  cx = a[n/2] - a[n/2 - 1]+1;
			lli  cy = b[n/2] - b[n/2 - 1]+1;
			lli ans=cx*cy;
			cout<<ans<<endl;
		    }
		    }
		    else
		 {
		    sort(a,a+n);
		   sort(b,b+n);
		if(n%2==0)
		{
			lli  cx = a[n/2] - a[n/2 - 1]+1;
			lli  cy = b[n/2] - b[n/2 - 1]+1;
			lli ans=cx*cy;
			cout<<ans<<endl;
		} 
		else 
		{
			cout<<1<<endl;
		}
		}
		}
  /* lli o=*min_element(a,a+n);
   lli h=*max_element(a,a+n);
   lli p=*max_element(b,b+n);
   lli r=*min_element(b,b+n);
   lli u=min(o,r);
   lli y=max(h,p);
   vector<lli>v;
   for(lli i=u;i<=y;i++)
   {
       for(lli j=u;j<=y;j++)
       {
           lli ans=calc(a,b,n,i,j);
           v.pb(ans);
       }
   }
   map<lli,lli>mp;
   sort(v.begin(),v.end());
   for(auto x:v)
   mp[x]++;
   lli res=mp[v[0]];
   cout<<res<<endl;
   */
}
}
### Prompt

Please create a solution in Cpp to the following problem:

You and your friends live in n houses. Each house is located on a 2D plane, in a point with integer coordinates. There might be different houses located in the same point. The mayor of the city is asking you for places for the building of the Eastern exhibition. You have to find the number of places (points with integer coordinates), so that the summary distance from all the houses to the exhibition is minimal. The exhibition can be built in the same point as some house. The distance between two points (x_1, y_1) and (x_2, y_2) is |x_1 - x_2| + |y_1 - y_2|, where |x| is the absolute value of x. 

Input

First line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 1000). Next n lines describe the positions of the houses (x_i, y_i) (0 ≤ x_i, y_i ≤ 10^9).

It's guaranteed that the sum of all n does not exceed 1000.

Output

For each test case output a single integer - the number of different positions for the exhibition. The exhibition can be built in the same point as some house.

Example

Input


6
3
0 0
2 0
1 2
4
1 0
0 2
2 3
3 1
4
0 0
0 1
1 0
1 1
2
0 0
1 1
2
0 0
2 0
2
0 0
0 0


Output


1
4
4
4
3
1

Note

Here are the images for the example test cases. Blue dots stand for the houses, green — possible positions for the exhibition.

<image>

First test case.

<image>

Second test case. <image>

Third test case. <image>

Fourth test case. <image>

Fifth test case. <image>

Sixth test case. Here both houses are located at (0, 0).

### Response

```cpp
// warm heart, wagging tail,and a smile just for you!
//                         _ _ _ __ __ __  __ _ _ __ _ _ __ _ __ ____ _ _ _ _ _ _ _ _ 
//                          ||__|| || ||\\//||  //__\\  ||\\ || ||__   ||__||  ||  ||
//                          ||  || || ||    || //    \\ || \\||  ___|| ||  ||  \\__//
//                                                    _ ___ _ _ _ _  _ __ _ _ __ _ __ _ __ _ _ __ ___ __ _ _ _ _ ___ _ _ ___
//                                                    ||__   ||__||  //__\\  ||\\ || ||// ||__|| ||  ]] ||__||  //__\\  ||__))
//                                                    ____|| ||  || //    \\ || \\|| ||\\ ||  || ||__]] ||  || //    \\ || \\
//                                                                     ¦¦¦¦¦¦¦¦¦¦¦
//                                                                   ¦¦¦++++++++++¦¦¦
//                                                                ¦¦¦+++++¦¦¦¦++++++¦¦¦
//                                            ¦¦¦¦¦¦¦¦¦¦¦       ¦¦+++++¦¦¦¦++¦¦¦¦+++++¦¦
//                                      ¦¦¦¦¦¦¦¦¦+++++¦¦¦¦¦¦¦¦¦¦¦¦+++++¦¦++++++¦¦¦+++++¦¦
//                               ¦¦¦¦¦¦¦¦++++++++++++++++++++++¦¦¦¦¦¦¦¦¦++++++¦¦+++++++¦¦
//                             ¦¦¦¦+¦¦+++++++++++++++++++++++++++++¦¦¦¦¦¦¦¦¦+++++++++++¦¦                 
//                           ¦¦¦+++¦++++++++++++++++++++++++++++++++++++¦¦++¦¦¦+++++++¦¦¦¦¦                                        
//                         ¦¦¦+++++++++++++++++++++++++++++++++++++++++++¦¦+++¦¦¦¦¦¦¦¦+++++¦¦                             
//                       ¦¦¦++++++++++++++++++++++++++++++++++++++++++++++++++++¦¦¦+++++++++¦¦¦              
//                     ¦¦¦++++++++++++++++++++++++++++++++++++++++++++++++++++++++¦¦¦¦¦+++++++¦¦             
//                 ¦¦¦¦++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++¦¦¦¦+++++¦¦¦¦
//     ¦¦¦¦¦¦¦¦¦¦¦¦¦++++++++¦¦+++++¦¦¦¦+++++++++++++++++¦¦¦¦¦+++++++++++++++++++++++++++¦¦¦++++¦¦¦¦¦¦            
//   ¦¦¦¦+++++++++++++++++++¦¦++¦¦¦¦¦¦+++++++++++++++++++++¦¦¦¦¦¦+++++++¦¦¦¦¦¦¦¦¦¦¦++++++++¦¦+++¦¦+++¦¦
// ¦¦¦++++++++++++++++++++¦¦+++++++++++++++++¦¦+++++++++++++++++++++¦¦¦¦+++++++++++¦+++++++¦¦++++++++¦¦
// ¦¦+++++++++++++++++++++¦¦++++¦¦¦¦¦¦+++¦¦¦¦++¦¦¦¦+++++++¦¦¦¦¦¦¦¦¦¦+++++++++++++++++++++++¦¦+++++++¦¦¦
// ¦¦+++++++++++++++++++++¦¦¦¦¦¦¦¦¦¦¦¦¦+++++++++++++++++++¦¦¦¦¦¦¦¦¦++++++++++++++++++++++++¦¦++++¦¦¦¦¦
// ¦¦¦++++++++++++++++++¦¦¦+++++¦¦++++++++++++++++++++++++++++¦¦¦¦¦++++++++++++++++++++++++¦¦¦¦¦¦¦¦
//   ¦¦¦+++++++++++++¦¦¦¦¦++++++++¦¦++++++++++++++++++++++++¦¦¦++¦¦+++++++++++++++++++++++¦¦
//       ¦¦¦¦¦¦¦¦¦¦¦¦¦¦  ¦¦¦¦++++++¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦+++++¦¦+++++++++++++++++++¦¦¦¦
//                         ¦¦¦¦¦¦¦                           ¦¦¦¦¦  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
//
//#include<boost/multiprecision/cpp_int.hpp>
#include <bits/stdc++.h>
const long double pi = 3.1415926535897932384626433832795;
#define scn(n) scanf("%d",&n)

#define lscn(n) scanf("%lld ",&n)

#define scn2(n1,n2) scanf("%d%d",&n1,&n2)

#define lscn2(n1,n2) scanf("%lld%lld",&n1,&n2)

#define lpri(n) printf("%lld ",n)

#define lpri2(n1,n2) printf("%lld %lld\n",n1,n2)

#define pri(n) printf("%d ",n)

#define pri2(n1,n2) printf("%d %d\n",n1,n2)

#define pln() printf("\n")

#define priln(n) printf("%d\n",n)

#define lpriln(n) printf("%lld\n",n)

#define RAL(i,x,n) for(int i=x;i<n;i++)

#define RALR(i,x,n) for(int i=x-1;i>=n;i--)
//insert function in vector is used to insert a value at given index
//ex: v.insert(v.begin(),10); inserts 10 at 0th position in vector 

//vector.resize(3) is used to resize the size of given array 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define mp make_pair

#define F first

#define S second
#define sq(a) (a)*(a)
#include<unordered_set>
#define lli long long int
#define toh_shuru_karte_hai_bina_kise_bakchodi_ke ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define test lli t;cin>>t;while(t--)
#define arrin lli n;cin>>n;lli a[n];for(lli i=0;i<n;i++)cin>>a[i]       // a%b=a-b*floor(a/b);
#define floop for(lli i=0;i<n;i++)
#define mod 1000000007
#define defvec vector<lli>v
#define ub upper_bound
#define pb push_back
#define pob pop_back
#define mp make_pair
#define emp emplace_back
#define bs binary_search
#define pi 3.1415926536
#define INF ll(8230219982008199610)
#define MINF ll(-8230219982008199610)
#define ones(n) __builtin_popcountll(n)
#define focc(n) __builtin_ffsll(n) //to count index of first 1 from right in binary representation of a number starting from index 1
#define leadingzero(n) __builtin_clzll(n)
#define trailingzeroes(n) __builtin_ctzll(n)
#define loop0(i,n) for(int i=0; i<n; i++)
#define loop1(i,n) for(int i=1; i<=n; i++)
#define rev0(i,n)  for(int i=n-1; i>=0; i--)
#define rev1(i,n)  for(int i=n; i>0; i--)
#define code lli n,k;cin>>n>>k;lli a[n];loop0(i,n) cin>>a[i]
#define loopj(j,k,n) for(lli j=k;j<n;j++)
#define all(x) x.begin(), x.end()
#define print(v) for(auto x:v)cout<<x<<" "
#define prints for(lli i=0;s[i];i++)cout<<s[i]
//using namespace boost::multiprecision ;
//typedef long long ll;
//typedef vector<lli> vi;
//typedef pair<lli,lli> pi;
using namespace std;

//atoll(s.c_str())  to convert string s into long long int
//all_of(a,a+n,ispositive());  //to check all the elements in array are positive
//any_of(a,a+n,ispositive());  //to check any element in array is positive
//none_of(a,a+n,ispositive());  //to check none of the elements in array is positive
//copy_n(a,n,b);  //to copy all the elements from a to b
//iota(a,a+n,10); //this will print consequtive n terms starting from 10 //ex if n=5 than 10,11,12,13,14
//same can be used for character array

//a number is divisible by 8 if last three digits of it is divisible by 8
//ex. 1512 as 512 is divisible by 8 so 1512 is also divisible by 8

/* NUMBER OF WAYS TO PLACE TWO QUEENS ON A BOARD OF SIZE n*n SUCH THAT THEY DO NOT ATTACK ON EACH OTHER
   count=(pow(n,4)/2)-(5*(pow(n,3)/3)+(3*pow(n,2)/2)-n/3;
*/
/* bitset<10>s;
  s[0]=1;
  s[3]=1;
  s[5]=1;
  s[7]=1;
  cout<<s;
 output is 1001010100
  cout<<s.count();
  output is frequency of 1 so 4

*/

// a number is power of 4 if num>0 && log2(num)/2==(int)log2(num)/2

#define INT_BITS 16
//if(abs(a-b)<1e-9)                  //TO COMPARE FLOATING POINT INTEGER
//{  
//    a and b are equal
//}

//string s=R"(HIMANS&\nSHAN\t)"; we can print a whole string same as given by doing this
//vector<int>v={1,2,3,4};
//vector<int>w=move(v);
//after this v={};
//w={1,2,3,4};
// to reverse a string reverse(str.begin(), str.end());
//  OR
// string rev = string(str.rbegin(),str.rend());

//q.front() operation works in queue but not works in priority_queue
//so for priority_queue q.top() is used
// ~x=-(x+1)  ex: ~29=-30;

unsigned lli leftRotate(unsigned lli n, unsigned lli d) 
{ 
    return (n << d)|(n >> (INT_BITS - d)); 
} 
unsigned lli rightRotate(unsigned lli n,unsigned lli d) 
{ 
    return (n >> d)|(n << (INT_BITS - d)); 
} 
//TO SET Kth BIT AS ONE n|(1<<k) while n&(~(1<<k)) sets the kth bit of n to 0
//and n^(1<<k) inverts the kth bit of n
//The number of digits of an integer x in base b can be calculated using the formula
//[logb(x) + 1]. For example, [log3(17) + 1] = 3.
//Every composite number has at least one prime factor less than or equal to square root of itself
int log2(int x)
{
  int res=0;
  while(x>>=1)
  res++;
  return res;
}
lli comb(lli n,lli r)

{
    
if(r==0||r==n)
           //VALUE OF nCr
return 1;
    
return 
comb(n-1,r)+comb(n-1,r-1);

}
bool isPowerOfTwo(int n) 
{ 
   if(n==0) 
   return false; 
  
   return (ceil(log2(n)) == floor(log2(n))); 
} 
lli inverse(lli a,lli m)
{
    return 1<a?m-inverse(m%a,a)*(m/a):1;    //for fastly calculate inverse modulo
}
lli issorted(lli arr[], lli n) 

{ 
 if (n == 1 || n == 0) 
        
return 1; 
  
 
if(arr[n - 1] < arr[n - 2]) 
       
return 0; 
  


return issorted(arr, n - 1); 

} 

int computeXOR(int n)
{
  if(n%4==0)
  return n;                        //TO CALCULATE XOR FROM 1 TO N
  if(n%4==1)
  return 1;
  if(n%4==2)
  return n+1;
  else
  return 0;
}

lli count(string s)//count distinct element in string
{
    lli ans=1,i,j;
    for(i=1;i<s.length();i++)
    {
        for(j=0;j<i;j++)
        {
            if(s[i]==s[j])
            break;
        }
        if(i==j)
        ans++;
    }
    return ans;
}

bool isPerfectSquare(long double x) 

{   
  // Find floating point value of  
  
// square root of x. 
  
long double sr = sqrt(x); 
  
  
// If square root is an integer 
  
return ((sr - floor(sr)) == 0); 

} 

lli countarray(lli a[],lli n)//count distinct element in array
{
  unordered_set<lli>s;
for(lli i=0;i<n;i++)
s.insert(a[i]);
return s.size();
}



bool check (int N)          //to check whether ith bit of n is 1 or 0
    {  lli i;
        if( N & (1 << i) )
            return true;
        else
            return false;
    }



bool isvowel(char ch)      
{
    string s = "aeiouAEIOU";
    for (char c : s)
    {
        if (c == ch)
        {
            return true;
        }
    }
    return false;
}



bool isPrime(lli n) 
{ 
    if(n<=1)  return false; 
    if(n<=3)  return true; 
    if(n%2==0||n%3==0) return false; 
    for(lli i=5; i*i<=n; i=i+6) 
    if (n%i == 0 || n%(i+2) == 0) 
    return false; 
    return true; 
}



struct interval

{
    int start,end;
   
 
};
                                             //SORTING IN A SPECIAL ORDER
bool compare(interval x,interval y)

{
    return (x.start<y.start);
}


bool isSubstring(string s1, string s2) 
{ 
    int M = s1.length(); 
    int N = s2.length(); 
  
    /* A loop to slide pat[] one by one */
    for (int i = 0; i <= N - M; i++) { 
        int j; 
  
        /* For current index i, check for 
 pattern match */
        for (j = 0; j < M; j++) 
            if (s2[i + j] != s1[j]) 
                break; 
  
        if (j == M) 
            return true; 
    } 
  
    return false; 
} 

int count_primes_in_range(int n)  //to count number of primes from 1 to n
{
   
bool isprime[n+1];
    
for(int i=2;i<=n;i++)
    
isprime[i]=true;
    
isprime[0]=false;
    
isprime[1]=false;
    
for(int i=2;i<=sqrt(n);i++)
    
{   
if(isprime[i]==true)
       
{
           
for(int j=i*i;j<=n;j+=i)
        
{
           
isprime[j]=false;
               
}

}
      
    
}
    
int count=0;
    
for(int i=0;i<=n;i++)
    
{
        
if(isprime[i]==true)
        
count++;
    
}
    
return count;

}



void multiply(int a[2][2],int m[2][2])

{                                                 //
int him[2][2];
                                    //   MATRIX EXPONENTIATION
for(int i=0;i<2;i++)
                              //
{   
                                              //
for(int j=0;j<2;j++)
        
{   him[i][j]=0;
            
for(int k=0;k<2;k++)
            
{
                
him[i][j]+=(a[i][k]*m[k][j]);
            
}
            
        
}
    
}
    
for(int i=0;i<2;i++)
    
{
        for(int j=0;j<2;j++)
        
{
            a[i][j]=him[i][j];
        
}
    
}
}
void power(int a[2][2],int n)

{   if(n==0||n==1)
    
return;
    
power(a,n/2);
    
multiply(a,a);
    
if(n%2!=0)
    
{  
int m[2][2]={{1,1},{1,0}};
        
multiply(a,m);
    
}

}
int fib(int n)

{
    
int a[2][2]={{1,1},{1,0}};
    
if(n==0)
    
return 0;
    
power(a,n-1);
    
return a[0][0];

}




lli power_(lli a,lli n) 
{ 
    lli res = 1;      
   
    while (n > 0) 
    { 
        if (n& 1) 
            res = ((res)*(a)); 
        n/=2; 
        a=((a)*(a));
    } 
    return res; 
}
int factmod(int n, int p) {
    vector<int> f(p);
    f[0] = 1;
    for (int i = 1; i < p; i++)
        f[i] = f[i-1] * i % p;

    int res = 1;
    while (n > 1) {
        if ((n/p) % 2)
            res = p - res;
        res = res * f[n%p] % p;
        n /= p;
    }
    return res; 
}

lli modularexponentiation(lli a,lli n,lli mo) 
{ 
    lli res = 1;      
   
    while (n > 0) 
    { 
        if (n& 1) 
            res = ((res%mo)*(a%mo))%mo; 
        n/=2; 
        a=((a%mo)*(a%mo))%mo;
    } 
    return res; 
}



lli largest_power(lli N)
    {                                              //LARGEST POWER OF 2 JUST LESS THAN OR EQUAL TO A GIVEN 16 BIT NUMBER
        //changing all right side bits to 1.
        N = N| (N>>1);
        N = N| (N>>2);
        N = N| (N>>4);
        N = N| (N>>8);
        N = N| (N>>16);  

    //as now the number is 2 * x-1, where x is required answer, so adding 1 and dividing it by
                return (N+1)>>1;

    }

bool alternate(lli n)
{
    lli i;
    if((n^(n>>1))==(pow(2,i)-1))           //this is to check that in binary representation of n, n has alternate sequence or not
    return true;                             //ex.101010          if n^(n>>1) is like this 11111 or containing only set bits than yes otherwise no  
return false;
}

    lli countDivisors(lli n) 
{ 
    lli cnt = 0; 
    for (int i = 1; i <= sqrt(n); i++) { 
        if (n % i == 0) { 
            // If divisors are equal, 
            // count only one 
            if (n / i == i) 
                cnt++; 
  
            else // Otherwise count both 
                cnt = cnt + 2; 
        } 
    } 
    return cnt;
}


int highestpowerof2(int n)   //highest power of 2 which divides a given number
{
    return (n&(~(n-1)));
}

/*lli dectobin(lli n)
{                                           //DECIMAL TO BINARY FOR A 32 BIT INTEGER
for (int i = 31; i >= 0; i--) {
if (n&(1<<i)) cout << "1";
else cout << "0";
}
}*/
/*lli maxfrequency(lli v[],lli n)
{    lli n;
		cin >> n;
                lli a[n];
		vector<lli> cnt(n + 1);
		for (int i = 0; i < n; ++i) {
			cin>>a[i];
			++cnt[a[i]];
		}
		lli mx = *max_element(cnt.begin(), cnt.end());
		lli diff = n + 1 - count(cnt.begin(), cnt.end(), 0);//COUNT OF DIFFERENT ELEMENTS PRESENT IN ARRAY
return mx;
}*/
void lowertoupper(char ch)
{
   ch=ch&'_';
  cout<<ch<<" ";
}
void uppertolower(char ch)
{
  ch=ch|' ';
  cout<<ch<<" ";
}
lli primecounter(lli l,lli r)
{                              //this counts prime in range l to r both inclusive
   lli fact=1,count=0;
   for(lli i=l;i<=r;i++)
   {
      if(((fact-i)%((1LL<<i)-1))==0)
      count++;
    fact*=((1LL<<i)-1);
   }
  return count;
} 
lli counteprime(lli l,lli r)
{
   lli count=0,i,j;
  for(i=l;i<=r;i++)           //THIS WILL ALSO GIVE COUNT OF PRIMES IN RANGE L TO R
  {
     for(j=2;j<=(i/j);j++)
     {
       if(!(i%j))
       break;
     }
      if(j>(i/j))
      count++;
   }
return count;
}
void pairsort(int a[], char b[], int n)     //SORT AN ARRAY ACCORDING TO SECOND ARRAY
{ 
    pair<int, char> pairt[n]; 
  
    // Storing the respective array 
    // elements in pairs. 
    for (int i = 0; i < n; i++)  
    { 
        pairt[i].first = a[i]; 
        pairt[i].second = b[i]; 
    } 
  
    // Sorting the pair array. 
    sort(pairt, pairt + n); 
      
    // Modifying original arrays 
    for (int i = 0; i < n; i++)  
    { 
        a[i] = pairt[i].first; 
        b[i] = pairt[i].second; 
    } 
} 
lli fibo(lli n)
{
    long double him=(1+sqrt(5))/2;
  return round(pow(him,n)/sqrt(5));
}
lli binToDec(string c) 
{  
    lli count=0;
    for(lli i=0;i<c.length();i++)
   {
       if (c[i] == '1'){
            lli val = 1;
           for(lli j=0;j<i;j++)
           {
                val *= 2;
            }
            count += val;
        }
   }
   return count;
} 
void rev(int a[],int n)
{
        for(lli i=0,j=n-1;i<j;i++,j--)
        {
            swap(a[i],a[j]);
        }
        loop0(i,n)
        cout<<a[i]<<" ";
}
/*void concatenate(int arr1[], int arr2[], int m, int n) 
{ 
   memcpy(arr1 + m, arr2, sizeof(arr2));    //TO CONCATENATE TWO ARRAYS
} */
vector<lli> Eratosthenes(int n) 
{
    vector<lli> res;
    vector<bool> Prime(n + 1, true);
    Prime[0] = Prime[1] = false;
    for(int i=4;i<=n;i+=2)
    {
        Prime[i]=false;
    }
    for (int i = 3; i * i <= n; i+=2) 
    {
        if (Prime[i]) 
        {
            for (int j = i*i; j <= n; j+=i) 
            {
                if(Prime[j]==true)
                Prime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++) 
    {
        if (Prime[i]) 
        {
            res.emplace_back(i);
        }
    }
    return res;
}
bool isvalid(lli x,lli y,lli n,lli m)
{
    if(x<0||x>(n-1)||y<0||y>(m-1))
    return false;
    //if(visited[x][y]==true)
    //return false;
    return true;
}
lli bs(lli a[],lli start,lli end,lli x,lli n)
{
    lli mid=start+(end-start)/2;
    if(start>end)
    return -1;
    if(a[mid]==x)
    return mid;
    else if(a[mid]>x)
    return bs(a,start,mid-1,x,n);
    else 
    return bs(a,mid+1,end,x,n);
}
void transpose(vector<vector<lli>>&v)
{
    loop0(i,v.size())
    {
        loop0(j,i)
        {
            swap(v[i][j],v[j][i]);
        }
    }
}
map<lli,lli> primeFactors(lli n)  
{  
    map<lli,lli>mp;
    while (n % 2 == 0)                          //PRIME FACTORISATION IN SQRT(n)
    {  
        mp[2]++;
        n=n/2;
    }  
    for (lli i = 3; i <= sqrt(n); i = i + 2)  
    {  
        while (n % i == 0)  
        {  
           mp[i]++;                 //PRIME FACTORIZATION
            n = n/i;  
        }  
    }  
    if (n > 2)  
        mp[n]++;
        /*for(auto x:mp)
        {
            cout<<x.first<<" "<<x.second<<endl;
        }*/
        return mp;
}  
void primefactors(lli n)
{                                     //PRIME FACTORISATION USING SIEVE
    lli d[n+1];
    memset(d,-1,sizeof(d));
    d[1]=1;
    for(lli i=2;i<=n;i+=2)
    {
        d[i]=i;
    }
    for(lli i=3;i<=n;i+=2)
    {
        if(d[i]==-1)
        {
            for(lli j=i;j<=n;j+=i)
            {
                if(d[j]==-1)
                {
                    d[j]=i;
                }
            }
        }
    }
    
    // for(lli i=1;i<=n;i++)
    // cout<<d[i]<<" ";
    map<lli,lli>mp;
    while(n>1)
    {
        mp[d[n]]++;
        n=n/d[n];
    }
   // for(auto x:mp)
    //cout<<x.first<<" "<<x.second<<endl;
}
lli gcd (lli a, lli b) {
    return b ? gcd (b, a % b) : a;
}
lli lcm (lli a,lli b) {
    return a / gcd(a, b) * b;
}
lli SubArraySum(lli arr[] ,lli n ) 
{ 
    lli result = 0; 
    for (lli i=0; i<n; i++) 
        result += (arr[i] * (i+1) * (n-i)); 
    return result ; 
} 
lli countsetbits(lli n)
{
    lli count=0;
    while(n)
    {
        count++;
        n=n&(n-1);
    }
    return count;
}
lli nCr(lli n,lli k) 
{
    double res = 1;
    for (lli i = 1; i <= k; ++i)
        res = res * (n - k + i) / i;
    return (int)(res + 0.01);
}
lli gcd_(lli a,lli b) 
{
    if (!a || !b)      //if a==0 || b==0 than simply return other element
        return a | b;
    unsigned shift = __builtin_ctzll(a | b);  //this will count min 2 factor in both numbers
    a >>= __builtin_ctzll(a);
    do {
        b >>= __builtin_ctzll(b);
        if (a > b)
            swap(a, b);
        b -= a;
    } while (b);
    //finally b will become 0 and a will contain our result
    return a << shift;
}
pair<lli,lli> fib (lli n) {
    if (n == 0)
        return {0ll, 1ll};
                                                             //FIBONACCI IN logN
    auto p = fib(n >> 1ll);
    lli c = ((p.first%mod)*((2 * (p.second%mod))%mod - (p.first%mod)+mod)%mod)%mod;
    c=c%mod;
    lli d =((((p.first%mod) * (p.first%mod))%mod) + ((p.second%mod) * (p.second%mod))%mod)%mod;
    d=d%mod;
    lli x=(c+d)%mod;
    if (n%2!=0)
        return {d,x};
    else
        return {c, d};
}
lli nCrModPFermat(lli n, lli r)
{
    if (n < r)
        return 0;
    if (r == 0)
        return 1;
    lli fac[n + 1];
    fac[0] = 1;
    for (lli i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % mod;
 
    lli ans=((fac[n] %mod)* modularexponentiation(fac[r],mod-2,mod)) % mod;
    ans=(ans*modularexponentiation(fac[n - r], mod-2,mod)) % mod;
    return ans;
}
lli calc(lli a[],lli b[],lli n,lli x,lli y)
{
    lli sum=0;
    loop0(i,n)
    {
        sum+=abs(a[i]-x)+abs(b[i]-y);
    }
    return sum;
}
int main()
{
   toh_shuru_karte_hai_bina_kise_bakchodi_ke;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
test{
   lli n;
   cin>>n;
   lli a[n],b[n];
   loop0(i,n)
   cin>>a[i]>>b[i];
   vector<pair<lli,lli>>v;
   loop0(i,n)
   v.pb({a[i],b[i]});
		if(n==1)
		{
			cout<<1<<endl;
		}
		else
		{
		    if(n==2)
		    {
		        if((v[0].first == v[1].first) || (v[0].second == v[1].second))
		     {
		         lli ans=abs(v[0].first-v[1].first)+abs(v[0].second-v[1].second)+1;
			cout<<ans<<endl;
		    }
		    else
		    {
		      sort(a,a+n);
		   sort(b,b+n);
		   lli  cx = a[n/2] - a[n/2 - 1]+1;
			lli  cy = b[n/2] - b[n/2 - 1]+1;
			lli ans=cx*cy;
			cout<<ans<<endl;
		    }
		    }
		    else
		 {
		    sort(a,a+n);
		   sort(b,b+n);
		if(n%2==0)
		{
			lli  cx = a[n/2] - a[n/2 - 1]+1;
			lli  cy = b[n/2] - b[n/2 - 1]+1;
			lli ans=cx*cy;
			cout<<ans<<endl;
		} 
		else 
		{
			cout<<1<<endl;
		}
		}
		}
  /* lli o=*min_element(a,a+n);
   lli h=*max_element(a,a+n);
   lli p=*max_element(b,b+n);
   lli r=*min_element(b,b+n);
   lli u=min(o,r);
   lli y=max(h,p);
   vector<lli>v;
   for(lli i=u;i<=y;i++)
   {
       for(lli j=u;j<=y;j++)
       {
           lli ans=calc(a,b,n,i,j);
           v.pb(ans);
       }
   }
   map<lli,lli>mp;
   sort(v.begin(),v.end());
   for(auto x:v)
   mp[x]++;
   lli res=mp[v[0]];
   cout<<res<<endl;
   */
}
}
```