import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.container;
import std.datetime;

void main()
{
	auto res = iota(0, 1000001).array;

	foreach_reverse (i; 0..1000001) {
		foreach (y; 2..1001) {
			auto py = y ^^ 2;	
			if (i + py > 1000000) break;
			res[i+py] = res[i] + y;
		}
	}

	foreach_reverse (i; 0..1000001) {
		foreach (z; 2..101) {
			auto pz = z ^^ 3;
			if (i + pz > 1000000) break;
			res[i+pz] = min(res[i+pz], res[i] + z);
		}
	}
	
	while (1) {
		auto n = readln.chomp.to!int;
		if (!n) break;
		res[n].writeln;
	}
}