격자의 모든 정수점 를 생각하자. 여기서 , 이다.
정수점 는 이면 검은 점, 이면 하얀 점이다.
서로 다른 세 점 를 고르자. 세 점이 한 직선 위에 있으면 삼각형을 만들 수 없으므로 세지 않는다.
에서 로 향하는 벡터와 에서 로 향하는 벡터가 만드는 평행사변형의 넓이를 라 하자.
세 점이 모두 같은 색이고, 가 소수이면 이 세 점을 좋은 삼각형이라고 한다.
주어진 에 대해 좋은 삼각형의 개수를 구하여라. 삼각형은 세 점의 집합으로 보며, 같은 세 점을 고르는 순서만 다른 경우는 하나로 센다.
답은 으로 나눈 나머지를 출력한다.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 좋은 삼각형의 개수를 으로 나눈 나머지를 한 줄에 하나씩 출력한다.
격자에서는 같은 색인 세 점을 고를 수 없다.
격자에는 좋은 삼각형이 개, 격자에는 좋은 삼각형이 개 있다.
는 테스트 케이스의 개수이다.
