HALD - Hiccup And Lucky Dragons

no tags 

Hiccup is the king of Viking village of Berk which is full of dragons. Like every year, Dragon War contest is going to be organized in Berk in which dragons fight till certain time limit and winning group of dragons are embraced asĀ  lucky dragon group for the village. Each dragon is characterized by its unique power level Pi. There are N dragons in the village with each dragon having a power level in the range [1,N]. No two dragons have the same power level. Hiccup does not want Dragons to fight so he comes up with a new strategy to select the required group of Dragons. He tells the villagers the he had a dream last night in which his father told him that a group of dragons will be lucky for the village if following two conditions are satisfied:

  1. There are at least two dragons in the group.
  2. Difference in the power level of any two dragons in the group is at least two.

Hiccup is going to choose any random lucky group of dragons to avoid the Dragon War but first he wants to know how many such groups are possible.

Input

First line of input contains T i.e. number of test cases. Next T lines contains an integer N denoting number of dragons in the village followed by an integer M.

Output

Print (number of lucky dragon groups possible) % M for each N

Constraints:

1 <= T <= 100000
1 <= N <= 10^18
1 <= M <= 10^18

Example

Input:
2
1 3
3 2 Output: 0
1

Explanation of sample input, n = 3 and m = 2:

There will be 3 dragons with power level 1, 2, 3 respectively.
Only 1 group can be chosen i.e. {1, 3}. So answer is (1 % 2) = 1


hide comments
[Rampage] Blue.Mary: 2016-02-04 12:45:38

This problem is about constant optimization.

reiji_azuma: 2015-07-18 16:58:27

O(T log n) is giving TLE. The time limit is way too strict. Not mentioning about the 10^18, due to it there is a need to use unsigned long long int which may lead in some solutions to WA. It's pretty pointless to give such a strict time limit. I would halve the T and make N <= 10^16, so that solutions slower than O(T log N) won't pass, but there are no problems with the type for input.

Last edit: 2015-07-18 16:58:45
:.Mohib.:: 2015-03-27 12:58:56

What is the answer for
1
100 7

Rajat De: 2015-03-24 12:00:37

time limit is way too strict

RIVU DAS: 2015-03-23 19:15:10

The same solution which got accepted during the contest is giving TLE here. Any reasons?
Re (XeRoN!X): Time limit is strict here.

Last edit: 2015-03-23 20:32:36

Added by:XeRoN!X
Date:2015-03-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Alkhwarizm 2015