lglg最近爱上了炒股，他想在股票市场内买一些股票。
lglg是一个很挑剔的人，他只喜欢编号为质数的股票，但他很有钱，因此他希望买下所有编号小于等于N(1<=N<=1e8)并且编号为质数的股票，请你帮他算一算这些股票的价值之和。
由于价值和很大，他希望你能告诉他价值之和对P(1e3<=P<=1e5)取模后的值。
输入包含多组数据 第一行是一个正整数 T(1<=T<=1000)，代表数据的组数。
每组数据只有一行，包含两个正整数 N 和 P 数字之间用空格隔开，其代表的含义及范围已在题面中给出。
每组数据输出一行，表示lglg希望买下的所有股票的价值之和对P取模后的值