Check cube

Level 4
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

#1 39
#2 18
#3 1
#4 12
#5 1
#6 2
#7 4
#8 8
#9 15
#10 4
#11 13
#12 8
#13 9
#14 13
#15 31
#16 24
#17 2
#18 9
#19 4
#20 10
#21 7
#22 10
#23 14
#24 8
#25 21
#26 34
#27 3
#28 17
#29 13
#30 1
#31 2
#32 3
#33 6
#34 36
#35 1
#36 16
#37 8
#38 2
#39 11
#40 7
#41 26
#42 19
#43 11
#44 23
#45 27
#46 2
#47 19
#48 2
#49 16
#50 4
Time: 1.579000000 s.

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>
#include <time.h>
using namespace std;

int oo = 2000000000;

int T, n, result;

int cube[51];

int maxx(int a, int b) { return (a>b ? a : b); }

int minn(int a, int b) { return (a<b ? a : b); }

void updateCubes(){
	for(int i = 1; i <= 50; i++){
		cube[i] = i*i*i;
	}
}

void backtrack(int index, int sum, int from){
	if(!sum){
		result++;
		return;
	}
	if(index == 5) return;

	
	for(int i = from; i > 0; i--){
		backtrack(index + 1, sum - cube[i], i);
	}
}

int main(){

	freopen("input.txt", "r", stdin);

	// Calc clock
	clock_t time_start, time_end; 
	time_start = clock(); 
	
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		// Initial && Input
		cin >> n;
		result = 0;

		// Solve Problem
		updateCubes();
		int m;
		for(int i = 1; i <= 50; i++){
			if(cube[i] <= n) m = i;
			else break;
		}
		backtrack(0, n, m);
		
		// Output
		cout << "#" << tc << " " << (result) << endl;
	}

	// Calc Time
	time_end = clock();
	cout.setf(ios::fixed);
	cout.precision(9);
	cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl;
	
	return 0;
 }