무한한 평면을 크기가 같은 다이아몬드 모양의 타일로 채우려고 한다. 이때 다음과 같은 조건이 있다.

1) (0, 0)은 항상 어떤 다이아몬드의 중앙에 있다.

2) 다이아몬드의 한 변의 길이는 자연수 n에 대해, n*sqrt2로 표현할 수 있다. 즉 다이아몬드의 두 대각선의 길이는 2*n이다.

3) 다이아몬드의 두 대각선은 각각 x축, y축과 평행하며, 정사각형 모양이다.

4) 빈 공간이 없어야 한다.

5) 다이아몬드의 변끼리 정확히 맞닿아있어야 한다. 즉, 45도 기울여서 봤을 때 전체가 격자 모양이어야 한다.

여러분은 무슨 이유에서인지 어떤 점 (a, b)에 대해, 이 점이 어떤 타일의 꼭짓점에 있도록 하고 싶다.

위 조건을 만족하는 타일 배치의 개수를 구하여라.

<Subtask>

#1 (17점) : T ≤ 10000, a, b ≤ 100

#2 (49점) : T ≤ 10000

#3 (34점) : 제한 없음

타일 채우기 timer 1s memory 1024MB

타일 채우기 1s 1024MB