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