Given a grid graph sized $$$10^5\times10^5$$$, with every original node split into 4 different nodes, as the following shows.

After splitting every node, now we get the graph like this.

In this way, every node in the new graph can be identified as $$$(a,b)c$$$, which means the $$$c(0\le c\le 3)$$$-th splitted node of the original node $$$(a,b)$$$, as the image above.

It is required to calculate the length of the shortest path from $$$(0,0)c$$$ to $$$(a,b)d$$$, and count the ways, modulo $$$998,244,353$$$, of doing so. There are $$$T$$$ test cases, and $$$T,a,b\le 10^5$$$, so we should solve it in $$$\Theta(1)$$$'s time. Note that every edge's length is $$$1$$$.

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;
constexpr ll mod=998244353;

ll fac[6000010], ifac[6000010];
ll qpow(ll x, ll y) {
  if (y < 0)
    y += mod - 1;
  ll res = 1;
  for (; y; y >>= 1) {
    if (y & 1) {
      res *= x;
      res %= mod;
    }
    x *= x;
    x %= mod;
  }
  return res;
}
void init() {
  fac[0] = 1;
  rep(i, 1, 6000005)
    fac[i] = fac[i-1] * i % mod;
  ifac[6000005] = qpow(fac[6000005], -1);
  drep(i, 6000005, 1)
    ifac[i-1] = ifac[i] * i % mod;
}
ll choose(int x, int y) {
  return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
ll F(int x,int y){
  return qpow(2,y)*choose(x+y,y)%mod;
}
ll G(int x,int y){
  return qpow(2,y-1)*choose(x+y-1,x-1)%mod*(y+2*x)%mod*qpow(x,-1)%mod;
}
pair<int,ll> s0(int b,int c,int d){
  int dis=(b-1)*2+b+(c!=0)+(c==2)+(d!=2)+(d==0);
  int cnt=b-1+(c==2)+(d==0);
  return {dis,qpow(2,cnt)};
}
pair<int,ll>C3(int a,int b){
  if (!a||!b)return s0(a^b,a?1:0,a?2:3);
  else if (a>b)return {3*a+b-1,G(b,a-b)};
  else return {a+3*b-1,G(a,b-a)};
}
pair<int,ll>C2(int a,int b){
  if (a>=b){ // T(a+2,b+1)
    auto [d1,c1]=C3(b,a);
    auto [d2,c2]=C3(b-1,a);
    ++d1,++++d2;
    ll cc=0;
    if (d1==min(d1,d2))cc+=c1;
    if (d2==min(d1,d2))cc+=c2;
    return {min(d1,d2),cc%mod};
  }
  else return {a+3*b-2,F(a,b-a-1)};
}
pair<int,ll>calc0(int a,int b,int d){
  return d==2?C2(a,b):C3(a,b);
}
pair<int,ll>calc(int a,int b,int d){
  if (d==2||d==3)return calc0(a,b,d);
  auto [d1,c1]=calc0(a,b,2);
  auto [d2,c2]=calc0(a,b,3);
  d1+=(d!=2)+(d==0);
  d2+=(d!=3)+(d==1);
  ll cc=0;
  if (d1==min(d1,d2))cc+=c1;
  if (d2==min(d1,d2))cc+=c2;
  // cout<<c1<<' '<<c2<<' '<<cc<<'\n';
  return {min(d1,d2),cc%mod};
}
void solve(){
  int a,b,c,d;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  if (!a&&!b){
    if (!(c^d))puts("0 1");
    else if ((c^d)==2)puts("2 2");
    else puts("1 1");
    return ;
  }else if (!a||!b){
    if (!b)c^=1,d^=1,swap(a,b);
    auto [dis,cnt]=s0(b,c,d);
    printf("%d %lld\n",dis,cnt);
    return ;
  }
  if (c&1)c^=1,d^=1,swap(a,b);
  if (!c){
    auto [dis,cnt]=calc(a,b,d);
    printf("%d %lld\n",dis,cnt);
    return ;
  }
  if (c==2){
    // cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n';
    auto [d1,c1]=calc(b,a,d^1);
    auto [d2,c2]=calc(a,b,d);
    ++d1,++++d2;
    ll cc=0;
    if (d1==min(d1,d2))cc+=c1;
    if (d2==min(d1,d2))cc+=c2;
    printf("%d %lld\n",min(d1,d2),cc%mod);
  }
}
int main() {
  init();
  int tt;
  for (scanf("%d",&tt);tt--;solve());
  return 0;
}

Additionally, define $$$T(n,k)=0$$$ when $$$n<0,k<0$$$. Then, $$$T(n,k)=2T(n-1,k)+T(n-1,k-1)$$$ except when $$$n=0,1,2$$$ and $$$k=0$$$. The difference is $$$1,-2,1$$$ respectively.

Because for example, $$$T(1,0)$$$ should have been $$$2$$$ when $$$T(0,0)=1$$$, but it gives $$$0$$$, so the difference is $$$-2$$$. The others are the same.

Let $$$G(x,y)=\sum\limits_{n}\sum\limits_{k}T(n,k)x^ny^k$$$. Then $$$G(x,y)=1-2x+x^2+2xG(x,y)+xyG(x,y)$$$, which means $$$G(x,y)=\dfrac{1-2x+x^2}{1-2x-xy}$$$.

It is easy to see $$$2xG(x,y)+xyG(x,y)$$$, because $$$T(n,k)=2T(n-1,k)+T(n-1,k-1)$$$. In the first part $$$n$$$ moved $$$1$$$, and the coefficient is $$$2$$$, so the contribution is $$$2\times x^1=2x$$$. The second part $$$n,k$$$ all moved $$$1$$$ and the coefficient is $$$1$$$, so the contribution is $$$x^1\times y^1=xy$$$.

And when $$$n=k=0$$$, the difference is $$$1$$$. So it is $$$1\times x^0\times y^0$$$, which is just $$$1$$$. For $$$n=1,k=0$$$, it's $$$-2\times x^1\times y^0$$$; and for $$$n=2,k=0$$$ it's $$$1\times x^2\times y^0$$$.

You can solve the equation and get the formula for the g.f..