Problem: Kate has finally calmed down and decides to forgive Little Deepu, but she won't forgive him just like that. She agrees to forgive him on the grounds that he can solve a mathematical question for her. 
She gives Deepu a large number N and a prime number P and asks him to calculate ((3*N)! / (3!^N) )%P.Your task is to help Little Deepu get back together with Kate.

Input
First line contains number of test cases T.
Next T lines contain two integers N and P, where P is a prime.  

Output
For each test case output the result ( (3*N)! / (3!)^N ) % P.  

Constraints:
1 ≤ T ≤ 10000
1 ≤ N ≤ 333333333
1 ≤ P ≤ 1000000000
1 ≤ abs(3*N-P) ≤ 1000  

SAMPLE INPUT
2
3 11
2 11

SAMPLE OUTPUT
8
9

Solution (in PYTHON):

Solution:
def extendedgcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

# inverse of a mod m
def modinv(a, m):
    gcd, x, y = extendedgcd(a, m)
    if gcd != 1:
        return None
    else:
        return x % m

def factmod(n,m):
    ans=1
    if n<=m//2:
        for i in xrange(1,n+1):
            ans=(ans*i)%m
    else:
        for i in xrange(n+1,m):
            ans=(ans*i)%m
        ans=modinv(ans,m)
        ans=-1*ans+m
    return ans%m
def mod_pow(base,exp,mod):
    rst=1
    while exp:
        if exp%2:
            rst=(rst*base)%mod
        base,exp=(base*base)%mod,exp//2
    return rst  
t=input()
while t!=0:
    n,p=map(int,raw_input().split())
    if 3*n>=p:
        print 0
    else:    
     a=factmod(3*n,p)
     b=mod_pow(6,n,p)
     c=modinv(b,p)
     print ((a%p)*(c%p))%p
    t-=1