Given three integers , , and , you need to color each lattice point in the set on the 2D Cartesian coordinate system using one of colors. Calculate the number of valid coloring methods. Two methods are considered different if and only if there exists one point in set with a different color between them.

This problem seems too simple, so Sauden adds a constraint: for any integers and , if the points and have the same color, the points and must also have the same color. Determine the number of valid coloring methods modulo .

The first line contains an integer  (), the number of test cases. 

Each test case consists of one line with three integers , , and  (, ), as described in the problem.

For each test case, output a single integer on a line, representing the answer modulo .

2
2 3 3
4 4 3

405
2413071