파스칼 삼각형

NYPC 2021 · 예선

파스칼 삼각형은 다음과 같은 성질을 만족하는 수로 이루어진 정삼각형이다.

예를 들어, 파스칼 삼각형의 첫 여섯 줄을 나타내면 다음과 같다.

<그림 1> 파스칼 삼각형의 첫 여섯 줄
<그림 1> 파스칼 삼각형의 첫 여섯 줄

이제 파스칼 삼각형의 특정한 위치 하나 (예를 들어, aa 번째 줄 bb 번째 수라고 하자)를 고른 다음, 이 위치의 수가 꼭짓점이 되는 크기가 cc인 정삼각형을 다음과 같이 정의하자.

<그림 2> 파스칼 삼각형 내부의 정삼각형 예
<그림 2> 파스칼 삼각형 내부의 정삼각형 예

<그림 2>를 보자. 22 번째 줄 11 번째 수가 한 꼭짓점인 크기 22인 정삼각형은 파란색으로, 22 번째 줄 22 번째 수가 한 꼭짓점인 크기 22인 정삼각형은 초록색으로, 55 번째 줄 22 번째 수가 한 꼭짓점인 크기 11인 정삼각형은 빨간색으로, 55 번째 줄 44 번째 수가 한 꼭짓점인 크기 11인 정삼각형은 노란색으로 표시되어 있다.

이제 정삼각형 안의 수들의 합은 삼각형 안에 있는 수의 합이다. 예를 들어 <그림 2>의 경우 정삼각형 안의 수의 합은 모두 44이다.

무한한 크기의 파스칼 삼각형에 대해 다음과 같은 질의를 하려고 한다. 이 삼각형에 포함되는 정삼각형 중 안의 수의 합이 정확하게 KK인 경우는 모두 몇 가지인가? KK가 주어질 때 이 질의를 답하라.

입력 형식

첫 줄에 질의의 수를 나타내는 정수 TT가 주어진다. (1T40001 \le T \le 4\,000)

그 다음 TT 개의 줄에 걸쳐 각 질의를 나타내는 정수 KK가 주어진다. (1K10181 \le K \le 10^{18})

출력 형식

TT 개의 줄에 걸쳐, 무한한 크기의 파스칼 삼각형에서 정삼각형 안의 수들의 합이 정확하게 KK인 경우의 수를 출력한다. 만약 이러한 삼각형이 무수히 많다면, 1-1을 출력한다.

예제

입력

3 1 2 3

출력

-1 1 3

예제 설명

잘 생각해보면 정삼각형 내부의 수의 합이 11인 경우는 무수히 많음을 알 수 있고, 이 때 답은 1-1이다. 정삼각형 내부의 수의 합이 22인 경우는 둘째 줄의 22 하나로 이루어지는 정삼각형 뿐이다. 마지막으로, 정삼각형 내부의 수의 합이 33인 경우는 첫 줄과 둘째 줄로 이루어지는 1,1,11, 1, 1로 이루어지는 삼각형 하나와, 네 번째 줄의 33 하나로 이루어지는 정삼각형 둘, 모두 세 가지 경우가 있다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 17

K8000K \le 8\,000

종류 2: 21

K1000000K \le 1\,000\,000

종류 3: 25

K1012K \le 10^{12}

종류 4: 37

추가적인 제한 조건이 없음.

해설