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:) .