#230 Good Triangles

Loading problem...

Preparing the statement, recent submissions, and submit form.

Authors: fldyof

Statement

$N \times M$ 격자의 모든 정수점 $(x,y)$ 를 생각하자. 여기서 $1 \leq x \leq N$ , $1 \leq y \leq M$ 이다.

정수점 $(x,y)$ 는 $(x+y) \bmod 2 = 0$ 이면 검은 점, $(x+y) \bmod 2 = 1$ 이면 하얀 점이다.

서로 다른 세 점 $A,B,C$ 를 고르자. 세 점이 한 직선 위에 있으면 삼각형을 만들 수 없으므로 세지 않는다.

$A$ 에서 $B$ 로 향하는 벡터와 $A$ 에서 $C$ 로 향하는 벡터가 만드는 평행사변형의 넓이를 $W$ 라 하자.

세 점이 모두 같은 색이고, $W$ 가 소수이면 이 세 점을 좋은 삼각형이라고 한다.

주어진 $N,M$ 에 대해 좋은 삼각형의 개수를 구하여라. 삼각형은 세 점의 집합으로 보며, 같은 세 점을 고르는 순서만 다른 경우는 하나로 센다.

답은 $998244353$ 으로 나눈 나머지를 출력한다.

입력은 다음과 같은 형식으로 주어진다.

$T$ $N_1\ M_1$ $N_2\ M_2$ $\vdots$ $N_T\ M_T$

$T$ 는 테스트 케이스의 개수이다.

각 테스트 케이스마다 좋은 삼각형의 개수를 $998244353$ 으로 나눈 나머지를 한 줄에 하나씩 출력한다.

#	Score	Constraints
1	100	추가적인 제약조건이 없다.

Input

Output

0
2
8

$2 \times 2$ 격자에서는 같은 색인 세 점을 고를 수 없다.

$2 \times 3$ 격자에는 좋은 삼각형이 $2$ 개, $3 \times 3$ 격자에는 좋은 삼각형이 $8$ 개 있다.