#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        cout<<((n+1)/2)*((m+1)/2)<<"\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        if(n%2==0){
            if((n/2)%2==1) cout<<"-1\n";
            else{
                ll x=(n/2);
                cout<<(x*(x+1))/2-(n/4)<<"\n";
            }
        }
        else{
            ll x=(n-1)/2;
            cout<<(x*(x+1))/2<<"\n";
        }
    }
}

#include<bits/stdc++.h>
#define pi 3.14159265358979323846
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define iofast ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
//give sin(),cos() radian, and asin(),acos() gives you radian
vector<int> v[1000010];
bool ch[1000010];
ll cnt1,cnt0;
void DFS(int po,bool c){
	if(!c) cnt0++;
	else cnt1++;
	ch[po]=1;
	for(auto i:v[po]){
		if(!ch[i]){
			DFS(i,!c);
		}
	}
	return;
}
void solve(){
	int n,a,b;
	cnt1=0;
	cnt0=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		v[i].clear();
		ch[i]=0;
	}
	for(int i=1;i<n;i++){
		cin>>a>>b;
		v[a].eb(b);
		v[b].eb(a);
	}
	DFS(1,0);
	cout<<(((cnt1-1)*cnt1)/2)+(((cnt0-1)*cnt0)/2)<<'\n';
	return;
}
int main(){
	iofast
	int t;
	cin>>t;
	w(t) solve();
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n,k;
        cin>>n>>k;
        if(k<n || k>(n*(n+1))/2) cout<<"-1\n";
        else{
            if(k==n){
                for(ll i=1;i<n;i++) cout<<i<<" ";
                cout<<0<<"\n";
            }
            else if(k==(n*(n+1))/2){
                for(ll i=0;i<n;i++) cout<<i<<" ";
                cout<<"\n";
            }
            else{
                k-=n;
                vector<ll> ans(n);
                ll val=0,ind=0,ind1=0;
                for(ll i=0;i<n;i++) ans[i]=i;
                for(ll i=n-1;i>0;i--){
                    if(k>i) k-=i;
                    else{
                        swap(ans[i-1],ans[0]);
                        val=k;
                        ind=i;
                        break;
                    }
                }
                for(ll i=0;i<n;i++){
                    if(ans[i]==val){
                        ind1=i;
                        break;
                    }
                }
                swap(ans[ind],ans[ind1]);
                for(auto i:ans) cout<<i<<" ";
                cout<<"\n";
            }
        }
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
ll mod=998244353;
const ll N=5e5+10;
vector<ll> po;

int main(){
    fast;
    po.resize(N);
    po[0]=1;
    for(ll i=1;i<N;i++) po[i]=(2*po[i-1])%mod;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll> a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        vector<ll> dp(n);
        vector<vector<ll>> v(n,vector<ll>(30));
        vector<ll> val(30,0);
        for(ll i=0;i<n;i++){
            for(ll j=0;j<30;j++){
                v[i][j]=val[j];
                if((a[i]&(1<<j))>0) val[j]=1-val[j];
            }
        }
        vector<vector<ll>> dp1(30,vector<ll>(2));
        ll ans=0;
        for(ll i=0;i<n;i++){
            dp[i]=ans;
            for(ll j=0;j<30;j++){
                dp1[j][v[i][j]]=(dp1[j][v[i][j]]+((1<<j)*(po[max((ll)0,i-1)]))%mod)%mod;
            }
            for(ll j=0;j<30;j++){
                if((a[i]&(1<<j))>0) dp[i]=(dp[i]+dp1[j][v[i][j]])%mod;
                else dp[i]=(dp[i]+dp1[j][1-v[i][j]])%mod;
            }
            ans=(ans+dp[i])%mod;
        }
        cout<<dp[n-1]<<"\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

ll mod=1e9+7;
 
long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}
 
long long modular_inverse(long long n){
  return power(n,mod-2);
}
 
#define MAXN 2000005
 
long long factorial[MAXN];
long long invfact[MAXN];
 
void cfact(){
  long long i;
  factorial[0]=1;
  factorial[1]=1;
  for(i=2;i<MAXN;i++){
    factorial[i]=factorial[i-1]*i;
    factorial[i]%=mod;
  }
  invfact[MAXN-1]=modular_inverse(factorial[MAXN-1]);
  for(i=MAXN-2;i>=0;i--){
    invfact[i]=invfact[i+1]*(i+1);
    invfact[i]%=mod;
  }
}
 
long long calcnCr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}

int main(){
    fast;
    cfact();
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        string s1,s2;
        cin>>s1>>s2;
        ll cnt11=count(s1.begin(),s1.end(),'1');
        ll cnt20=count(s2.begin(),s2.end(),'0');
        if(cnt11>0 && cnt20>0) cout<<"0\n";
        else if(cnt11==0 && cnt20>0) cout<<power((power(2,n)-1)%mod,n-cnt20)%mod<<"\n";
        else if(cnt11>0 && cnt20==0) cout<<power((power(2,n)-1)%mod,n-cnt11)%mod<<"\n";
        else{
            ll res=0;
            for(ll i=0;i<n;i++){
                if(i%2==0){
                    res=(res-((calcnCr(n,i+1))*power(2,n*n-(i+1)*n))%mod+mod)%mod;
                }
                else{
                    res=(res+((calcnCr(n,i+1))*power(2,n*n-(i+1)*n))%mod)%mod;
                }
            }
            cout<<(power(2,n*n)+2*res)%mod<<"\n";
        }
    }
}

WLOG, assume that x>=y. We desire for Alice to win. Let us check the scenarios where this is possible:

Case 1: (x>=2*y) This means Alice has to subtract a multiple of y from x. There are, say k choices of subtracting y, 2*y, .., k*y. We have >1 choices. If k*y is winning, Alice chooses that. If it is losing, then since (k>1), Alice can choose (k-1)*y and Bob will then be forces to subtract y in the next move, essentially making Bob choose the losing (k*y) state. So Alice always wins.

Case 2: (x<2*y): This means there is only one possible move, which is to subtract y from x. We get the pair of numbers (y,x-y) is losing, Alice wins. Else she loses.

Now, For her to loose, like in Case 1, (y>=2*(x-y)) (we already know y is larger than (x-y) since x < 2*y). So for her to win, y<(2*(x-y)), which means (x>(3/2)*y).

If (y<2*(x-y)), we again subtract and go to the next iteration. The new pair is (x-y, 2y-x). For it the winning conditions come out to be x>=(5/3)*y.

If we keep doing the iterations, we observe that in the nth step the condition comes out to be x>=(F(n+1)/F(n))*y where F(n) is the nth Fibonacci number. So, to get the exact bound, we take its limit as n approaches infinity, and get: Alice wins iff (x>phi*y) (phi=golden ratio).

So our problem becomes counting the number of (l,r) such that r>phi*y. Since our numbers <=1e9, we can take an appropriate approximation of phi, (say p/q).

Now our problem boils down to calculatig sum of floor(xq/p) for x from some index l' till r. (here l' is the first index such that floor(l'q/p)>=l).

This is a standard problem and can be calculated in O(log(max(x,y)) complexity. Here is reference a blog with exact details about solving this: https://www.cnblogs.com/apjifengc/p/17492207.html

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

const ll P = 998244353;
const ld phi=1.61803398874989;
const ll a=1134903170, b=0, c=1836311903;

struct Node {
    ll x, y, sumx, sumy;
    Node() : x(0), y(0), sumx(0), sumy(0) {}
    Node operator*(Node b) {
        Node a = *this, c;
        c.x = (a.x + b.x) % P;
        c.y = (a.y + b.y) % P;
        c.sumx = (a.sumx + b.sumx + a.x * b.x) % P;
        c.sumy = (a.sumy + b.sumy + a.y * b.x) % P;
        return c;
    }
};
Node pow(Node a, ll b) {
    Node ans;
    while (b) {
        if (b & 1ll) ans = ans * a;
        a = a * a;
        b >>= 1ll;
    }
    return ans;
}
Node euclid(ll p, ll q, ll r, ll n, Node U, Node R) {
    if (!n) return Node();
    if (r >= q) return pow(U, r / q) * euclid(p, q, r % q, n, U, R);
    if (p >= q) return euclid(p % q, q, r, n, U, pow(U, p / q) * R);
    ll m = (1ll * p * n + r) / q;
    if (!m) return pow(R, n);
    return pow(R, (q - r - 1) / p) * U * euclid(q, p, (q - r - 1) % p, m - 1, R, U) * pow(R, n - (q * m - r - 1) / p);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    Node U, R;
    U.y = 1, R.x = 1, R.sumx = 1;
    int t;cin>>t;while (t--){
    ll l, r;cin>>l>>r;
    ll sp=ceil(phi*l);
    ll fa=(r-l+1)%P;
    if (sp<=r){
    ll ne=r-sp+1;
    fa=(fa-((ne*(l-1))%P)+4*P)%P;
    auto ans_r = euclid(a, c, b, r, U, R);
        ans_r.sumy = (ans_r.sumy + (b / c)) % P;
        auto ans_sp = euclid(a, c, b, sp-1, U, R);
        ans_sp.sumy = (ans_sp.sumy + (b / c)) % P;
        fa=(fa+ans_r.sumy-ans_sp.sumy+5*P)%P;
    }
    cout<<fa<<endl;
    }
    return 0;
}