A vertex-colored rectangle is a rectangle whose four vertices are all painted with colors. For a vertex-colored rectangle, it's harmonious if and only if we can find two adjacent vertices with the same color, while the other two vertices also have the same color with each other.

For example, , and are harmonious, while is not (same number for same color, and different numbers for different colors).

For each point in , where is the set of all integers, Kotori wants to paint it into one of the three colors: red, blue, yellow. She wonders the number of different ways to color them so that there exists at least one harmonious rectangle formed by the points, whose edges are all parallel to the - or -axis. That is to say, there exists and such that

Two coloring plans are considered different if there exists a point having different colors in the two coloring plans.

There are multiple test cases. The first line of the input contains an integer  () indicating the number of test cases. For each test case:

The first and only line contains three integers , ().

For each test case output one line containing one integer indicating the number of different ways of coloring modulo .

3
1 4
2 2
3 3

0
15
16485