import java.util.ArrayList;
import java.util.List;

public class KPrimes {
	public static long[] countKprimes (int k, long start, long end) {
		List<Long> result = new ArrayList<>();

		for (long i = start == 0 ? 2 : start; i <= end; i++) {
			int numOfFactors = 0;
			long cur = i;

			for (int j = 2; j <= cur / j; j++) {
				while (cur % j == 0) {
					numOfFactors++;
					cur /= j;
				}
			}

			if (cur > 1) {
				numOfFactors++;
			}

			if (numOfFactors == k) result.add(i);
		}

		return result.stream().mapToLong(l -> l).toArray();
	}

	public static int puzzle (int s) {
		int combinations = 0;

		long[] onePrimes = countKprimes(1, 2, s);
		long[] threePrimes = countKprimes(3, 2, s);
		long[] sevenPrimes = countKprimes(7, 2, s);

		for (long i : onePrimes) {
			for (long j : threePrimes) {
				for (long k : sevenPrimes) {
					if (i + j + k == s) combinations++;
				}
			}
		}

		return combinations;
	}
}