Winnie has a small list of integers consisting of primes, and . Winnie wants to make the list larger, so Winnie will take two indices and in the list and add to the end of the list. She does this operation times. After the first time, she cannot choose two indices that have been multiplied together before. That is, the pair must not have been used before. In addition, she will always take the two indices that multiply together to yield the smallest value. Winnie is interested in the product of all elements in the final list after the operation is performed times. ~~Since C++ doesn't have BigInteger for some reason~~ Since this number may be very large, find this number modulo .

**There will be test cases.**

#### Input Specification

The first line will contain the integer , the number of test cases.

The next lines will each contain three integers . and are primes.

#### Output Specification

Output lines, the line will contain the answer to the test case. In particular, on the line, you should output the product of the integers in the final list, modulo .

It may help to know that .

#### Constraints

##### Subtask 1 [10%]

##### Subtask 2 [25%]

##### Subtask 3 [20%]

##### Subtask 4 [45%]

No additional constraints.

#### Sample Input 1

```
1
3 2 3
```

#### Sample Output 1

`7776`

#### Explanation For Sample 1

The first integer she adds to the list is . Then, the smallest product of the elements at two distinct indices that she hasn't used before is (She will choose ). For the last operation, the smallest product is (She will choose ). The final list is , and the product of these integers is .

#### Sample Input 2

```
1
10 2 3
```

#### Sample Output 2

`357454510`

## Comments