FIBTWIST - Fibonacci With a Twist

Fibonacci numbers are given by 

  • f(n) = f(n-1) + f(n-2)

with f(0) = 0 and f(1) = 1.

first number of series ------ 0  1  1  2  3  5  8  13 

Now let's have a new series called "Fibonacci Twist" which is given by 

  • ft(n) = ft(n-1) + ft(n-2) + (n-1)

with ft(0) = 0 and ft(1) = 1.

with first few number in the series ----- 0  1  2  5  10  19  34  59 

Now your task is to find ft(n).

Since the number can be big you have to find the result mod M.

Input

first line having single number 't' -- number of test cases.

Next t lines have 2 number each 'n' and 'M'

Output

Single number given the n-th term mod M

Example

Input:
3
5 20
10 77
15 111

Output:
19
45
69

Constraints

  • 10 <= t <= 100
  • 0 <= n <= 10^9
  • 100 <= M <= 10^9

Explanation

  1. ft(5) is 19. 19 % 20 = 19
  2. ft(10) is 276. 276 % 77 = 45
  3. ft(15) is 3177. 3177 % 111 = 69

Added by:Devil D
Date:2012-04-19
Time limit:0.100s-1s
Source limit:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own

hide comments
2013-05-09 07:11:50 Arika Saputro
can reduced to 2x2 matrix ;D
2013-05-01 13:10:08 Brian Curcio
One of my accepted solutions is actually giving wrong answer. Test cases are weak

1
456564654 999999999
-121092846


Last edit: 2013-05-01 13:10:54
2013-02-27 18:19:34 yaswanth
0.03 AC :)
2013-02-18 06:23:39 errorcode15


Last edit: 2013-02-18 09:13:27
2013-02-01 09:16:13 Pankaj Gudlani
more test cases please...
it is giving WA... :(
2013-01-22 09:49:11 符号器
@pranshul..agreed with u...
2012-12-19 05:37:41 $!:D
O(n) giving tle :(
is dere any other way to do it ?

Last edit: 2012-12-19 05:38:11
2012-12-18 10:12:27 triveni
for those , getting wrong answer: use mod(%) function cleverly . This may give wrong answer. I got one WA for that..
finally AC :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.