#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin>>T;
  while(T--){
    long long N,X;
    cin>>N>>X;
    if(X%2){
      cout<<(N+1)/2%mod<<'\n';
    }else{
      cout<<(N/(X+1)*(X/2+1)+N%(X+1)/2)%mod<<'\n';
    }
  }  
}