题目描述

Rivest 是密码学专家。近日他正在研究一种数列 $E= \{E_1,E_2,\cdots,E_n\}$，且 $E_1=E_2=p$（ $p$ 为一个质数），$E_i=E_{i-2}\times E_{i-1}$（若 $2<i\leq n$）。

` 例如 $\{2,2,4,8,32,256,8192,\cdots\}$ 就是 $p = 2$ 的数列。在此基础上他又设计了一种加密算法，该算法可以通过一个密钥 $q$($q < p$) 将一个正整数 $n$ 加密成另外一个正整数 $d$，计算公式为：$d = E_n \bmod q$。现在Rivest 想对一组数据进行加密，但他对程序设计不太感兴趣，请你帮助他设计一个数据加密程序。 输入格式： 第一行读入 $m,p$。其中 $m$ 表示数据个数，$p$ 用来生成数列 $E$。 以下有 $m$ 行，每行有 $2$ 个整数 $n,q$。$n$ 为待加密数据，$q$ 为密钥。 数据范围：$0<p_n<2^{31},0<q<p_0<m\leq5000$。 输出格式： 将加密后的数据按顺序输出到文件 第i行输出第i个加密后的数据。

2 7 
4 5 
4 6

3
1

4 7 
2 4 
7 1 
6 5 
9 3

3
0
1
1