문제
무한한 평면을 크기가 같은 다이아몬드 모양의 타일로 채우려고 한다. 이때 다음과 같은 조건이 있다.
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점) : 제한 없음
입력
첫 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 106)
그 이후 T개의 줄에 걸쳐 두 정수 a와 b가 주어진다. (0 ≤ a,b ≤ 107)
출력
각 테스트 케이스마다 점(a, b)가 타일의 꼭짓점에 위치하도록 타일을 배치하는 방법의 수를 한 줄에 출력하시오.
예제1
입력
3
14
00
09
출력
1
0
3
예제2
입력
3
51
43
24
출력
0
1
1
출처
COCI 2022/2023 Contest #1 4번