PKU 2853. Sequence Sum Possibilities

연속된 수들의 합으로 나타낼 수 있는 경우의 수(?)

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 3213	Accepted: 2159

설명

대부분의 양정수들은 최소 2개의 연속된 양정수들의 합으로 나타낼 수 있습니다. 예를 들어,

6 = 1 + 2 + 3
9 = 5 + 4 = 2 + 3 + 4

그러나 8은 이러한 표현이 불가능합니다.

이렇게, 입력된 숫자에 대해서 최소 2개 이상의 연속된 수들의 합으로 나타내는 방법이 얼마나 많이 있는지를 계산하는 프로그램을 작성하세요.

입력

첫 번째 줄은 계산할 숫자의 개수를 나타내는 N (1 ≤ N ≤ 1000)을 적습니다. 그 뒤로 나오는 N 개의 줄에는 각 줄에 계산해야 할 숫자가 하나씩 들어가는데, 각 줄에는 문제의 번호를 나타내는 숫자를 우선 넣고, 한 칸의 공백을 둔 뒤에 계산할 숫자를 넣습니다. 계산해야 할 숫자는 2의 31승보다는 작아야 합니다.

출력

각 문제를 출력할 때에는, 각 줄에 문제 번호를 쓰고 한 칸의 공백을 둔 뒤에 입력한 문제의 수를 연속된 양정수의 합으로 나타내는 방법의 수가 얼마나 있는지를 나타내면 됩니다.

입력 예시

7
1 6
2 9
3 8
4 1800
5 987654321
6 987654323
7 987654325

출력 예시

1 1
2 2
3 0
4 8
5 17
6 1
7 23

Source

Greater New York 2005


p.s: Mr.K의 의견을 수렴, 수정하였습니다.