问题 G: 小明的完美回文数

问题 G: 小明的完美回文数

时间限制: 1 Sec  内存限制: 128 MB
提交: 109  解决: 35
[状态] [讨论版] [提交] [命题人:]
题目描述

小明虽然发现了有趣回文数,但他觉得这种回文数不够完美。在他看来,偶数比素数更有意思,所以他将位数为偶数的回文数称为完美回文数。现在小明将所有的完美回文数从小到大进行排序,并算出前n个完美回文数的和,并将结果对p取模,聪明的你能在帮他一次吗?

输入

第一行输入一个整数T,代表实例的数量。(T <= 500)
每个实例输入两个整数n,p,意义如题中所示(1 ≤n≤ 100000, 1 ≤p≤ 1e9)。

输出

对于每个样例,输出一个整数,代表得到的结果。

样例输入 Copy
2
2 100
5 30
样例输出 Copy
33
15