홍준이와 균형 잡힌 테이블

3행 C열 표의 각 칸에 음이 아닌 정수를 채워 a + c = 2b를 만족하는 모든 세 칸의 합이 S가 되도록 하는 채우기 방법의 수를 구한다.

보통6조합론수학동적 계획법구현아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

행이 3개이고 열이 CC개인 빈 테이블과 정수 SS가 주어진다. 홍준이는 테이블의 모든 칸에 음이 아닌 정수를 하나씩 적어야 한다.

서로 다른 세 행에서 한 칸씩 고른 세 칸이 있을 때, 그중 한 칸의 중심이 나머지 두 칸의 중심을 이은 선분의 중점과 일치하면 이 세 칸을 균형 잡힌 세 칸이라고 한다. 세 칸이 1행, 2행, 3행의 각각 aa열, bb열, cc열에 있다고 하면 이 조건은 a+c=2ba + c = 2b와 같다. 아래 그림은 C=8C = 8일 때 균형 잡힌 세 칸의 예이다.

3행 8열 테이블에서 균형 잡힌 세 칸

홍준이는 균형 잡힌 세 칸의 모든 경우에 대해 그 세 칸에 적힌 수의 합이 SS가 되도록 테이블을 채우려고 한다. 두 테이블 AABB에서 A(i,j)A(i, j)B(i,j)B(i, j)를 각각 iijj열에 적힌 수라고 할 때, A(i,j)B(i,j)A(i, j) \neq B(i, j)ii, jj가 하나라도 있으면 두 테이블은 다르다고 본다. CCSS가 주어지면 홍준이가 적을 수 있는 테이블의 개수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 TT(1T1001 \le T \le 100)가 주어진다.

둘째 줄부터 TT개의 줄에 각 테스트 케이스의 CCSS(1C501 \le C \le 50, 0S500 \le S \le 50)가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스마다 가능한 테이블의 개수를 한 줄에 하나씩 출력한다.