Một biểu diễn của một số nguyên dương N dưới dạng tổng các số nguyên dương nhỏ hơn hoặc bằng N được gọi là partition của số N. Ví dụ với N =15 ta có thể biểu diễn: 15 = 1+2+3+4+5 = 1+2+1+7+1+2+1.

Một partition được gọi là thuận nghịch nếu đọc theo cả hai chiều đều được kết quả giống nhau. Ví dụ {1+2+1+7+1+2+1} là một partition của 15 thoả mãn tính chất thuận nghịch.

Một partition được gọi là thuận nghịch đệ quy nếu nửa bên trái của nó cũng thuận nghịch đệ quy hoặc rỗng. Với định nghĩa này, mỗi số N sẽ hiển nhiên sẽ có hai partition thuận nghịch đệ quy là dãy N số 1 và dãy chỉ gồm duy nhất số N.

Ví dụ, các partition thuận nghịch đệ quy của 7 là:

7, 1+5+1, 2+3+2, 1+1+3+1+1, 3+1+3, 1+1+1+1+1+1+1

Viết chương trình nhập vào số tự nhiên N và đưa ra số partition thuận nghịch đệ quy của N.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên 1 ≤ t ≤ 1000 là số lượng bộ test. Mỗi bộ test sẽ viết trên một dòng duy nhất một số nguyên N(N<=1000)

Dữ liệu ra

Với mỗi bộ dữ liệu vào, đưa ra một dòng gồm 2 số: số thứ tự bộ test và số lượng partition thuận nghịch đệ quy tương ứng. Hai số cách nhau bởi một dấu cách.