Your task in this problem is very straightforward. You are given a point in the cartesian plane (m, n) where m > 0 and n > 0. You start at (0, 0) and are allowed to make unit moves along the positive x-axis or the positive y-axis. In other word if you are at a point (x, y) you can move to either (x+1,y) or (x,y+1). Your task is to find out the total number of ways you can reach (m, n) from (0, 0) modulus K.

Input

First line contains 'T', the number of testcases. The next 'T' lines contain three space separated integers m, n, K 1 <= m, n <= 1,000 K<=1,000,000

Output

A single integer denoting the total number of paths mod K.

Example

Input: 
1
4 4 100
 
Output: 
70