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

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

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