Finding factorials are easy but they become large quickly that is why Lucky hate factorials. Today he have another task related to factorials.

For a given number n how many ways factorial n can expressed as a sum of two or more consecutive positive integers. Can you help lucky ?

Input

First line contains single integer T < 5001, next T lines followed by an integer N<10^8 and M<10^9.

where M is a prime number.

Output

Print the desired result mod M.

Example

Input:

1

3 7

Output:

1

Explanation:: 3! = 1+2+3 only one way.

Speed Adicts My best time for all cases is 1.57s. Best of Luck have fun:) .

题意：给定N，问N的阶乘可以表示为一段连续数字之和的方案数，答案模M。

思路：无。

最新文章

1. shell注释
2. Android实用代码七段（四）
3. PHP+MySQL存储数据出现中文乱码的问题
4. C# 常用数据库连接字符串【转】
5. hdu-5927 Auxiliary Set(树形dp)
6. 如何在视频处理控件TVideoGrabber中设置音频捕捉设备
7. qt opencv
8. C#实现XML文件数据库存储
9. ASP.NET Identity 身份验证和基于角色的授权
10. java阅读器hdfs单纯demo
11. linux使用crontab实现PHP执行定时任务
12. Sqlmap Tamper大全(1)
13. tomcat在centos下的操作
14. Windows上安装配置SSH教程（8）——综合应用：在Windows上使用手动方式实现SSH远程登陆与文件传输
15. BZOJ.5287.[AHOI HNOI2018]毒瘤(虚树 树形DP)
16. 多线程开发之二 NSOperation
17. python的py文件命名注意事项
18. 【Android开发日记】之入门篇（九）——Android四大组件之ContentProvider
19. 将已有的项目提交到GitHub
20. WPF Converter 使用复杂参数的方法

热门文章

1. Unix操作系统LD_PRELOAD简介
2. Javascript构造函数和原型
3. three.js 源代码凝视（九）Math/Matrix4.js
4. UP board 漫谈——从Atom到UP Board
5. electron 开发拆坑总结
6. weexpack build android 和 weexpack run android 报错 及 解决方案
7. Python正則表達式：怎样使用正則表達式
8. MYSQL时间戳的处理
9. APACHE局域网配置域名访问
10. Intel HEX文件解析