Winnie has a small list ~v~ of integers consisting of ~2~ primes, ~X~ and ~Y~. Winnie wants to make the list larger, so Winnie will take two indices ~i~ and ~j~ ~(1 \le i < j \le |v|)~ in the list and add ~v_i \times v_j~ to the end of the list. She does this operation ~N~ times. After the first time, she cannot choose two indices that have been multiplied together before. That is, the pair ~(i, j)~ 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 ~N~ times. Since C++ doesn't have BigInteger for some reason Since this number may be very large, find this number modulo ~998\,244\,353~.

There will be ~T~ test cases.

Input Specification

The first line will contain the integer ~T~ ~(T \in \{1, 20\})~, the number of test cases.

The next ~T~ lines will each contain three integers ~N, X, Y~ ~(1 \le N \le 10^{18}, 2 \le X < Y \le 10^9)~. ~X~ and ~Y~ are primes.

Output Specification

Output ~T~ lines, the ~i^\text{th}~ line will contain the answer to the ~i^\text{th}~ test case. In particular, on the ~i^\text{th}~ line, you should output the product of the integers in the final list, modulo ~998\,244\,353~.

It may help to know that ~998\,244\,353 = 119 \times 2^{23} + 1~.

Constraints

Subtask 1 [10%]

~N \le 100~

Subtask 2 [25%]

~N \le 10^5~

Subtask 3 [20%]

~X = 2~

~Y = 3~

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 ~6~. Then, the smallest product of the elements at two distinct indices that she hasn't used before is ~2 \times 6 = 12~ (She will choose ~i=1, j=3~). For the last operation, the smallest product is ~3 \times 6 = 18~ (She will choose ~i=2, j=3~). The final list is ~[2, 3, 6, 12, 18]~, and the product of these ~5~ integers is ~7776~.

Sample Input 2

1
10 2 3

Sample Output 2

357454510