众所周知，不朽的海豚生活在直线的另一侧，并以活海鸥为食，尽管联邦法律禁止将海鸥运送给它们（但这又是另一个故事了）。

著名的科学家 Leo O. Pisa 对不朽的海豚进行了深入研究，并做出了一些有趣的发现。例如，他发现一对海豚每年会产下一窝 2 只幼崽，而且幼崽需要整整一年才能成熟并开始产下自己的幼崽。因此，如果你从一对刚出生的海豚开始，在第 1 年结束时，你仍然只有一对海豚（现在已经成熟并准备繁殖）。在第 2 年结束时，你会有一窝新的幼崽，但你也会有一对成熟的成年海豚！第二年，它们会产下第二窝幼崽，而它们的第一窝幼崽也准备好开始产下自己的幼崽了。

每年，去年存在的所有海豚仍然存在。此外，两年前存在的所有海豚都会产下幼崽！然而，为了防止世界被不朽的海豚淹没，每当它们的数量达到十亿（$10^9$）对或更多时，就会有十亿对海豚神秘地消失。奇怪的是，有些年份种群会完全消失。当这种情况发生时，第二年就会奇迹般地出现一对。事实上，对于任何给定的年份 $Y$，存活的海豚对数为 $fib(Y) \pmod{10^9}$，其中 $fib(Y)$ 是著名的斐波那契数列中的第 $Y$ 项。

你的任务是编写一个程序，确定在给定年份结束时存活的不朽海豚对数，假设你从第 1 年年初的一对新生海豚开始。由于不朽的海豚相信宇宙将存在整整 $2^{48} = 281,474,976,710,656$ 年，因此你无需处理超过该年份的情况。

输入格式

输入的第一行包含一个整数 $P$ ($1 \le P \le 1000$)，表示随后的数据集数量。每个数据集应被独立且相同地处理。

每个数据集由一行输入组成，包含两个空格分隔的值。第一个值是整数 $K$，表示数据集编号。下一个值 $Y$ ($1 \le Y \le 2^{48}$) 是海豚存活的年数。

输出格式

对于每个数据集，输出一行。该行包含数据集编号 $K$、一个空格以及在 $Y$ 年结束时存活的不朽海豚对数。

样例

输入 1

11
1 1
2 2
3 8
4 20
5 46
6 60
7 3749999998
8 3749999999
9 3750000000
10 3750000001
11 281474976710656

输出 1

1 1
2 1
3 21
4 6765
5 836311903
6 8755920
7 499999999
8 500000001
9 0
10 500000001
11 309764667