题目描述

有 $T$ 组询问，每次询问给出两个数 $n,m$，满足 $0 \leq m \leq n$，你需要求出 $\sum\limits_{i=0}^m C(n,i)$。

由于这个数可能很大，你只需要求出这个值 $\bmod 998244353$ 后的结果。

输入格式

第一行一个正整数 $T$，表示询问个数。

接下来 $T$ 行每行两个非负整数 $n,m$，表示一组询问。

输出格式

$T$ 行每行一个 $[0,998244352]$ 的正整数，表示对应询问的答案。

样例

input

5
100000 23333
100000 98765
666623333 233336666
123456789 98765432
900000000 233333

output

780149589
470308993
115424175
217983531
61569534

数据范围与提示

共有 $10$ 个测试点，前 $2$ 个测试点满足 $T \leq 10$，$n \leq 10^5$。

第 $i$ 个 ($i \geq 3$) 测试点满足 $T=i-2$，$n \leq 9 \times 10^8$。$m$ 在 $[0,n]$ 均匀随机。