// 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;
   */
}
}