Untitled

Checking cube
Given a integer N. Find number of possible ways to represent N as a sum of at most five cubes.

Input

First line contains N.

1<=N<=125000.

Output

Output the result

Sample

Input

4

1
64

905

15436

 

Output
#1 1

#2 2

#3 0

#4 12

 

Giải thích:
+ Cách 1: 64 = 27 + 27 + 8 + 1 + 1
+ Cách 2: 64 = 64 + 0  + 0 + 0 + 0

50
88236
48656
13459
11728
36174
30156
4852
20681
30537
86072
90017
117168
37756
64019
100162
43119
11136
13121
10356
78102
101127
82690
81340
62017
34651
124902
29776
82925
100821
3244
124546
38922
119326
123570
22936
103654
70963
36213
113709
69648
76626
79011
84170
119374
66214
36590
71902
4877
109837
51232

#include <iostream>
using namespace std;

int n;
int visited[12501];
int ans;
int arr[6];

void BackTrack(int number, int m, int k){

	if(number == 0 && k == m){

		/*for(int j=1; j<=5; j++){
			cout << arr[j] << " ";
		}
		cout << endl;*/

		ans++;
		return;
	}

	if(number > 0 && k == m)
		return;

	for(int i=50; i>=1; i--){
		if(i*i*i <= number){
			if(i <= arr[k]){
				arr[k+1] = i;
				BackTrack(number - i*i*i, m, k + 1);
			}
		}

	}

}

int main(){
	//freopen("vao.txt", "r", stdin);
	int t;
	cin >> t;
	for(int tc=1; tc<=t; tc++){
		cin >> n;

		ans = 0;
		arr[0] = 51;

		for(int i=1; i<=5; i++){
			BackTrack(n, i, 0);
		}

		cout << "#" << tc << " ";
		cout << ans << endl;
	}
	return 0;
}