题目描述

你正在玩一个特殊的 2048 游戏。与普通模式不同，你需要在棋盘上连接出一条

的链来得分。连接的链越长，得分越高。

现在出现了一个诡异的残局。棋盘大小为 $n\times n$，行、列下标均从 $0$ 到 $n-1$。第 $i$ 行第 $j$ 列的数值恰好为

其中 $\oplus$ 表示按位异或。

请你求出：在最优情况下，能够连接出的链的最大长度，以及达到该最大长度的可行方案数。

输入格式

第一行包含一个整数 $t$，表示数据组数。

接下来 $t$ 行，每行包含两个整数 $l,n$，分别表示参数 $l$ 和棋盘大小 $n$。

输出格式

输出 $t$ 行。

每行输出两个整数，分别表示最优链长度和可行方案数。

由于方案数可能超过 long long 的范围，请将方案数对 $998244353$ 取模后输出。

样例

输入

4
1 1
1 2
1 3
2 2

输出

0 1
0 2
3 4
1 4

样例说明

样例 3 和样例 4 的可行连接方案如下图所示，红色数字表示被选入链中的格子。

数据范围

对于 $100\%$ 的数据：