REC - Recurrence


Let F0 = 1. Fn = a*Fn-1 + b for n >= 1. Find Fn (mod M).

Input

The first line contains T the number of test cases. Each of the next T lines contains 4 space separated integers a, b, n and M.

Constraints

T <= 20000
0 <= a, b, n <=  10^100
1 <= M <= 100000

Output

Output T lines, one corresponding to each test case.

Example

Input:
3
1 1 1 10
2 1 2 5
5 2 20 30

Output:
2
2
7

hide comments
The Mundane Programmer: 2012-06-12 18:43:53

getting NZEC in python 2.5 after .14 seconds...... give some more test cases

cjtoribio: 2011-07-23 06:00:05

@Miftakhul Khasanah
Check when M = 1 , N = 0

Lureohc Otnafifa: 2011-04-26 03:46:42

please somebody help me...What is the tricky testcase for this problems


Added by:abhijith reddy d
Date:2009-11-14
Time limit:1s-2.516s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP C++ 4.3.2 CPP CPP14 C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL WHITESPACE