SP13420 FMODF - Fimodacci

求斐波那契数列的第 $N$ 项模第 $K$ 项后的结果。

第一行，一个整数 $T$。 接下来有 $T$ 行，每行两个整数 $N,K$。

对于每行，输出第 $N$ 项模第 $K$ 项后的结果。

$T \le {10}^5$，$2 \le N \le 10^{18}$，$2 \le K \le 10^3$ **提示:该数列第 $1$ 项为 $1$ ,第 $2$ 项也为 $1$ ,其余每项是前两项之和。**