SUPERPW - SuperPower

You are given two arrays a and b of size n. You are also given a number p.

You are supposed to find ( a[0]^b[0] + a[1]^b[1] + ... a[n-1]^b[n-1] ) % p

You must also know that

( a + b ) % c = ( a%c + b%c ) % c

and

( a * b ) % c = ( a%c * b%c ) % c

Warning: The actual value a[i]^b[i] may not fit in any primitive data-type, infact it may not even fit in the RAM.

Input

First line contains T ( T <= 12 ) which is the number of test-cases.

Then contain T-blocks having the following format.

First line of each block contains a number n which is the number of elements of arrays a and b and the number p.

Second line of each block contains n-integers which are the values a[0], a[1] ... a[n-1]

Third line of each block contains n-integers which are the values b[0], b[1] ... b[n-1]

Output

For each block of input print the answer.

Example

Input:
2
3 5
2 3 4
1 1 1
4 4
2 2 2 2
1 1 1 1

Output:
4
0

Added by:.:: Pratik ::.
Date:2010-04-16
Time limit:1.417s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET

hide comments
2019-02-14 21:13:44
0 < n, p, a[i], b[i] < 50,000.
2013-08-15 05:22:14 John and the cows
why is the time limit so ... long ???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.