该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

斐波那契数列

题目背景

斐波那契数列（Fibonacci sequence），又称黄金分割数列 ，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递推的方法定义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

（以上内容来自百度百科）

由于斐波那契数列后面的数字很大，今年是 2024 年，所以小季想研究斐波那契数列模2024的结果。

题目描述

为了方便计算，我们记斐波那契数列为 $f$，它的递推式为

• $f_1 = 1$
• $f_2 = 1$
• $f_n = f_{n-1} + f_{n-2}$ ($n \ge 2$ 且 $n$ 为整数)

请求出 $f_n \ mod \ p$ , $p = 2024$ 的值，由于 $n$ 的值可能非常大，我们使用幂指数的形式来表示，即 $n = a^b$.

输入格式

输入包括多组数据。

第一行一个整数 $T$，代表数据组数。

接下来 $T$ 行，每行两个整数 $a$ 和 $b$，用空格隔开，含义见描述。

输出格式

对于每组数据，输出一行结果，代表 $f_n mod \ 2024 = f_{a^b}$ $mod \ 2024$ 的值。

样例输入

4
4 1
3 2
2 6
2024 2024

样例输出

3
34
619
987

数据范围及约定

对于所有数据， $1 \le T \le 100$。