Sol là một cậu bé có niềm đam mê đặc biệt với những con số. Cậu thích khám phá các quy luật và tạo ra những thử thách độc đáo để rèn luyện kỹ năng tính toán của mình. Một ngày nọ, khi dạo bước trong chợ làng, Sol nhìn thấy một người bán hàng bày ra một tấm thảm có in một lưới số kỳ lạ. Mỗi ô vuông được sắp xếp theo hàng và cột, tạo thành một ma trận số tuyệt đẹp. Bị cuốn hút, Sol hỏi người bán về ý nghĩa của nó và được biết rằng đây là một lưới bí ẩn với các quy luật ẩn giấu do người tạo ra nghĩ ra.

Bị vẻ đẹp ấy hấp dẫn, Sol quyết định tạo ra lưới của riêng mình, không phải là sự sắp xếp ngẫu nhiên của các con số, mà là một cấu trúc rõ ràng và logic. Cậu đã nghĩ ra một cách đặc biệt để điền số vào lưới:

1. Cấu trúc lưới:

   • Sol sẽ tạo một lưới kích thước ~M \times N~, với ~M~ hàng và ~N~ cột. Cậu tưởng tượng mỗi ô trong lưới như một ô vuông trống, sẵn sàng để được trang trí bằng những con số của mình.

2. Quy tắc điền số: Để giữ cho lưới hài hòa, Sol quyết định:

   • Ở ô nằm tại hàng ~i~ và cột ~j~, cậu sẽ điền số ~(i - 1) \times N + j~ nếu tổng ~(i + j)~ là số chẵn. Điều này đảm bảo rằng các ô ở vị trí hài hòa sẽ sáng lên với những con số theo quy luật.
   • Nếu tổng ~(i + j)~ là số lẻ, cậu sẽ điền ~0~ vào ô đó. Cách này tạo nên một mẫu xen kẽ giữa các ô nổi bật và trung tính, tạo ra sự đối xứng cuốn hút.

Nhiệm vụ:

Hãy giúp Sol tính tổng tất cả các số trong lưới theo quy tắc trên, lấy dư theo (C).

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên ~Q~, là số lượng truy vấn ~(Q \leq 10^5)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~M, N,~ và ~C~ ~(M, N, C \leq 10^{18})~.

Dữ liệu ra:

• Gồm ~Q~ dòng, mỗi dòng chứa một số nguyên: tổng các phần tử trong lưới theo modulo ~C~.

Ví dụ nhập

1
3 4 100

Ví dụ xuất

38

Ghi chú

• Lưới do Sol điền theo quy tắc như sau: