Sol is a boy with a peculiar passion for numbers. He enjoys discovering patterns and creating unique challenges to improve his calculation skills. One day, while strolling through the village market, he noticed a vendor displaying a peculiar grid of numbers on a mat. Each square was arranged in rows and columns, forming a beautiful numeric grid. Intrigued, Sol asked the vendor about its significance and was told that it was a mysterious grid with hidden patterns devised by its creator.

Fascinated by its beauty, Sol decided to create his own grid, not just a chaotic arrangement of numbers, but one following a clear and logical pattern. He devised a special way to fill the grid with numbers:

1. Grid Structure:

   • Sol would create a grid of size ~M \times N~, with ~M~ rows and ~N~ columns. He imagined each cell in the grid as an empty square, ready to be adorned with his numbers.

2. Filling Rules: To maintain harmony in the grid, Sol decided:

   • In the cell located at row ~i~ and column ~j~, he would fill the number ~(i - 1) \times N + j~ if the sum ~(i + j)~ is even. This ensures that cells in harmonious positions will glow with patterned numbers.
   • If the sum ~(i + j)~ is odd, he would fill the cell with ~0~. This creates an alternating pattern of highlighted and neutral cells, producing a fascinating symmetry.

Task:

Help Sol compute the sum of all numbers in the grid following the rules above, modulo (C).

Input:

• The first line contains an integer ~Q~, the number of queries ~(Q \leq 10^5)~.
• The next ~Q~ lines, each containing three positive integers ~M, N,~ and ~C~ ~(M, N, C \leq 10^{18})~.

Output:

• The output consists of ~Q~ lines, each containing a single integer: the sum of the grid elements modulo ~C~.

Sample Input

1
3 4 100

Sample Output

38

Notes

• The grid filled by Sol based on the rules is as follows: