다트

독일을 비롯한 여러 나라에는 둥글고 납작한 과녁에 작은 화살을 던지는 오래된 놀이가 있습니다. 이 작은 화살과 놀이를 모두 다트(darts)라고 부릅니다.

다트 과녁은 하나의 평평한 원으로 이루어져 있으며, 여러 개의 조각(slice)과 고리(ring)로 나뉩니다. 조각에는 1부터 20까지 번호가 매겨져 있고, 바깥쪽 두 고리는 각각 더블 링(double ring)과 트레블 링(treble ring)이라고 부릅니다. 과녁 한가운데는 불스아이(bull's eye)라고 하며, 다시 안쪽(진짜 불스아이)과 바깥쪽(불, bull)으로 나뉩니다.

그림: 다트 과녁의 구조.

점수 규칙은 다음과 같습니다. 번호가 $s$인 조각을 맞혔을 때, 싱글(단일 영역)이면 $s$점, 더블 링이면 $2s$점, 트레블 링이면 $3s$점을 얻습니다. 예를 들어 20번 조각을 더블 링에서 맞히면 2 × 20 = 40점입니다. 불스아이의 안쪽을 맞히면 50점, 바깥쪽(불)을 맞히면 25점입니다. 과녁을 벗어나 어떤 영역도 맞히지 못한 화살은 0점입니다.

한 턴은 화살 3개를 던지는 것으로 이루어지며, 그 턴의 점수는 세 화살이 얻은 점수의 합입니다.

어제 친구들이 다트를 했고, 그 경기의 점수가 아직 칠판에 남아 있습니다. 당신은 각 턴의 점수만 보고 세 화살이 과녁의 어느 영역을 맞혔을 수 있는지 알아내려 합니다. 한 턴의 점수가 주어졌을 때, 그 점수를 만들 수 있는 세 화살의 서로 다른 조합의 수를 구하는 프로그램을 작성하세요. 화살을 던진 순서는 구분하지 않습니다.

두 조합이 같은지는 "맞힌 영역"으로 판단합니다. 같은 조각을 같은 고리에서 맞혔거나, 같은 불을 맞혔거나, 둘 다 빗나간 경우에만 같은 화살로 봅니다. 점수가 같아도 맞힌 영역이 다르면(예: 싱글 3점과 트레블 1점) 서로 다른 화살로 셉니다.

예를 들어 턴 점수가 3인 경우는 다음과 같이 만들 수 있습니다.

3 = 0    + 0    + 1*3    한 화살이 싱글 3
3 = 0    + 0    + 3*1    한 화살이 트레블 링의 1
3 = 0    + 1*1  + 1*2    한 화살이 싱글 1, 한 화살이 싱글 2
3 = 0    + 1*1  + 2*1    한 화살이 싱글 1, 한 화살이 더블 링의 1
3 = 1*1  + 1*1  + 1*1    세 화살 모두 싱글 1

따라서 서로 다른 조합의 수는 5입니다.

조금 더 복잡한 예로 점수 9는 다음과 같은 조합들을 포함합니다.

9 = 0    + 0    + 1*9    한 화살이 싱글 9
9 = 0    + 0    + 3*3    한 화살이 트레블 링의 3
9 = 0    + 1*1  + 1*8    한 화살이 싱글 1, 한 화살이 싱글 8
9 = 0    + 1*1  + 2*4    한 화살이 싱글 1, 한 화살이 더블 링의 4
...
9 = 0    + 3*2  + 1*3    한 화살이 트레블 링의 2, 한 화살이 싱글 3
9 = 1*1  + 1*1  + 1*7    두 화살이 싱글 1, 한 화살이 싱글 7
...
9 = 2*1  + 3*1  + 2*2    더블 링의 1, 트레블 링의 1, 더블 링의 2
9 = 1*3  + 1*3  + 1*3    세 화살 모두 싱글 3
9 = 1*3  + 1*3  + 3*1    두 화살이 싱글 3, 한 화살이 트레블 링의 1
9 = 1*3  + 3*1  + 3*1    한 화살이 싱글 3, 두 화살이 트레블 링의 1
9 = 3*1  + 3*1  + 3*1    세 화살 모두 트레블 링의 1

이때 조합의 수는 얼마일까요? 이를 계산하는 프로그램을 작성하세요.

첫째 줄에 시나리오(턴)의 개수가 주어집니다.

이어지는 각 줄에는 시나리오가 하나씩 주어지며, 그 턴의 다트 점수가 하나의 양의 정수로 주어집니다.

각 시나리오마다 먼저 "Scenario #i:" 형식의 줄을 출력합니다. 여기서 $i$는 1부터 시작하는 시나리오 번호입니다. 그다음 줄에 그 점수를 만들 수 있는 서로 다른 다트 조합의 수를 출력합니다.

연속한 두 시나리오의 출력 사이에는 빈 줄을 하나 넣어 구분합니다.