题目描述

定义无穷序列 $f$：$\displaystyle f_1=1,f_n=f_{n-1}\times 2+1$。

定义函数 $\displaystyle G(x)=\min_{f_i\ge x}f_i$。

定义 $\displaystyle g_{c,0}=0,g_{c,i}=\max(g_{c,i-1},[((i\times c)\And G(i))=i]\times i)$。

求 $\displaystyle \sum^n_{i=0} g_{c,i} \bmod 998244353$。

输入格式

第一行输入一个整数 $T$，表示数据组数。

每组测试用例输入一行包含两个整数 $n,c$。

其中 $n$ 以二进制形式表示，且 $n$ 不含有前导 $0$。

输出格式

对于每组测试用例输出一行一个整数表示答案。

样例

5
1001 1
11111 1
101010111101 8999
10100101111010101 799
10010010 233

45
496
2835797
707482963
9940

数据范围

对于全部数据，$1\le T\le 10$，$1\le |n|\le 10^7$，$\sum |n|\le 10^7$，$1\le c\le 10^{18}$。