Jon and Joe have received equal marks in the school examination. But, they won't reconcile in peace when equated with each other. To prove his might, Jon challenges Joe to write a program to find all possible number combos that sum to a given number. While unsure whether he would be able to accomplish this feat or not, Joe accpets the challenge. Being Joe's friend, your task is to help him out.

# Task

Create a function `combos`, that accepts a single positive integer `num` (30 > `num` > 0) and returns an array of arrays of positive integers that sum to `num`.

# Notes
1. Sub-arrays may or may not have their elements sorted.
2. The order of sub-arrays inside the main array does not matter.
3. For an optimal solution, the following operation should complete within 6000ms.

# Sample

Difficulty: MEDIUM_HARD
Tags: Fundamentals

Mathematics

Complete search
Skill types: Complete search

Starter code:
def combos(n):
	

Solutions:
def combos(n, m=1):
	if n < m:
		return []
	res = [[n]]
	for i in xrange(m, n):
		l = [i]
		for j in combos(n - i, i):
			res += [l + j]
	return res


def combos(n):

	def partition(residue, acc):
		if residue == 0:
			yield acc[1:]
		else:
			for part in range(acc[-1], residue + 1):
				for result in partition(residue - part, acc + [part]):
					yield result
	return list(partition(n, [1]))


def combos(n, r=0):
	if n < 2 or r == 1:
		return [[1] * n]
	return sum([[c + [i] for c in combos(n - i, i)] for i in range(1, min(n, r or n) + 1)], [])


def combos(n):
	if n == 1:
		return [[1]]
	if n == 2:
		return [[1, 1], [2]]
	if n == 3:
		return [[1, 1, 1], [1, 2], [3]]
	if n == 4:
		return [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]
	if n == 5:
		return [[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 4], [2, 3], [5]]
	if n == 6:
		return [[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 2], [1, 1, 1, 3], [1, 1, 2, 2], [1, 1, 4], [1, 2, 3], [1, 5], [2, 2, 2], [2, 4], [3, 3], [6]]
	if n == 7:
		return [[1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 3], [1, 1, 1, 2, 2], [1, 1, 1, 4], [1, 1, 2, 3], [1, 1, 5], [1, 2, 2, 2], [1, 2, 4], [1, 3, 3], [1, 6], [2, 2, 3], [2, 5], [3, 4], [7]]
	if n == 8:
		return [[1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 4], [1, 1, 1, 2, 3], [1, 1, 1, 5], [1, 1, 2, 2, 2], [1, 1, 2, 4], [1, 1, 3, 3], [1, 1, 6], [1, 2, 2, 3], [1, 2, 5], [1, 3, 4], [1, 7], [2, 2, 2, 2], [2, 2, 4], [2, 3, 3], [2, 6], [3, 5], [4, 4], [8]]
	if n == 9:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 5], [1, 1, 1, 2, 2, 2], [1, 1, 1, 2, 4], [1, 1, 1, 3, 3], [1, 1, 1, 6], [1, 1, 2, 2, 3], [1, 1, 2, 5], [1, 1, 3, 4], [1, 1, 7], [1, 2, 2, 2, 2], [1, 2, 2, 4], [1, 2, 3, 3], [1, 2, 6], [1, 3, 5], [1, 4, 4], [1, 8], [2, 2, 2, 3], [2, 2, 5], [2, 3, 4], [2, 7], [3, 3, 3], [3, 6], [4, 5], [9]]
	if n == 10:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 6], [1, 1, 1, 2, 2, 3], [1, 1, 1, 2, 5], [1, 1, 1, 3, 4], [1, 1, 1, 7], [1, 1, 2, 2, 2, 2], [1, 1, 2, 2, 4], [1, 1, 2, 3, 3], [1, 1, 2, 6], [1, 1, 3, 5], [1, 1, 4, 4], [1, 1, 8], [1, 2, 2, 2, 3], [1, 2, 2, 5], [1, 2, 3, 4], [1, 2, 7], [1, 3, 3, 3], [1, 3, 6], [1, 4, 5], [1, 9], [2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5], [2, 4, 4], [2, 8], [3, 3, 4], [3, 7], [4, 6], [5, 5], [10]]
	if n == 11:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 7], [1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 2, 2, 4], [1, 1, 1, 2, 3, 3], [1, 1, 1, 2, 6], [1, 1, 1, 3, 5], [1, 1, 1, 4, 4], [1, 1, 1, 8], [1, 1, 2, 2, 2, 3], [1, 1, 2, 2, 5], [1, 1, 2, 3, 4], [1, 1, 2, 7], [1, 1, 3, 3, 3], [1, 1, 3, 6], [1, 1, 4, 5], [1, 1, 9], [1, 2, 2, 2, 2, 2], [1, 2, 2, 2, 4], [1, 2, 2, 3, 3], [1, 2, 2, 6], [1, 2, 3, 5], [1, 2, 4, 4], [1, 2, 8], [1, 3, 3, 4], [1, 3, 7], [1, 4, 6], [1, 5, 5], [1, 10], [2, 2, 2, 2, 3], [2, 2, 2, 5], [2, 2, 3, 4], [2, 2, 7], [2, 3, 3, 3], [2, 3, 6], [2, 4, 5], [2, 9], [3, 3, 5], [3, 4, 4], [3, 8], [4, 7], [5, 6], [11]]
	if n == 12:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 8], [1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 2, 2, 5], [1, 1, 1, 2, 3, 4], [1, 1, 1, 2, 7], [1, 1, 1, 3, 3, 3], [1, 1, 1, 3, 6], [1, 1, 1, 4, 5], [1, 1, 1, 9], [1, 1, 2, 2, 2, 2, 2], [1, 1, 2, 2, 2, 4], [1, 1, 2, 2, 3, 3], [1, 1, 2, 2, 6], [1, 1, 2, 3, 5], [1, 1, 2, 4, 4], [1, 1, 2, 8], [1, 1, 3, 3, 4], [1, 1, 3, 7], [1, 1, 4, 6], [1, 1, 5, 5], [1, 1, 10], [1, 2, 2, 2, 2, 3], [1, 2, 2, 2, 5], [1, 2, 2, 3, 4], [1, 2, 2, 7], [1, 2, 3, 3, 3], [1, 2, 3, 6], [1, 2, 4, 5], [1, 2, 9], [1, 3, 3, 5], [1, 3, 4, 4], [1, 3, 8], [1, 4, 7], [1, 5, 6], [1, 11], [2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 4], [2, 2, 2, 3, 3], [2, 2, 2, 6], [2, 2, 3, 5], [2, 2, 4, 4], [2, 2, 8], [2, 3, 3, 4], [2, 3, 7], [2, 4, 6], [2, 5, 5], [2, 10], [3, 3, 3, 3], [3, 3, 6], [3, 4, 5], [3, 9], [4, 4, 4], [4, 8], [5, 7], [6, 6], [12]]
	if n == 13:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 9], [1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 2, 2, 6], [1, 1, 1, 2, 3, 5], [1, 1, 1, 2, 4, 4], [1, 1, 1, 2, 8], [1, 1, 1, 3, 3, 4], [1, 1, 1, 3, 7], [1, 1, 1, 4, 6], [1, 1, 1, 5, 5], [1, 1, 1, 10], [1, 1, 2, 2, 2, 2, 3], [1, 1, 2, 2, 2, 5], [1, 1, 2, 2, 3, 4], [1, 1, 2, 2, 7], [1, 1, 2, 3, 3, 3], [1, 1, 2, 3, 6], [1, 1, 2, 4, 5], [1, 1, 2, 9], [1, 1, 3, 3, 5], [1, 1, 3, 4, 4], [1, 1, 3, 8], [1, 1, 4, 7], [1, 1, 5, 6], [1, 1, 11], [1, 2, 2, 2, 2, 2, 2], [1, 2, 2, 2, 2, 4], [1, 2, 2, 2, 3, 3], [1, 2, 2, 2, 6], [1, 2, 2, 3, 5], [1, 2, 2, 4, 4], [1, 2, 2, 8], [1, 2, 3, 3, 4], [1, 2, 3, 7], [1, 2, 4, 6], [1, 2, 5, 5], [1, 2, 10], [1, 3, 3, 3, 3], [1, 3, 3, 6], [1, 3, 4, 5], [1, 3, 9], [1, 4, 4, 4], [1, 4, 8], [1, 5, 7], [1, 6, 6], [1, 12], [2, 2, 2, 2, 2, 3], [2, 2, 2, 2, 5], [2, 2, 2, 3, 4], [2, 2, 2, 7], [2, 2, 3, 3, 3], [2, 2, 3, 6], [2, 2, 4, 5], [2, 2, 9], [2, 3, 3, 5], [2, 3, 4, 4], [2, 3, 8], [2, 4, 7], [2, 5, 6], [2, 11], [3, 3, 3, 4], [3, 3, 7], [3, 4, 6], [3, 5, 5], [3, 10], [4, 4, 5], [4, 9], [5, 8], [6, 7], [13]]
	if n == 14:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 10], [1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 2, 2, 7], [1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 2, 3, 6], [1, 1, 1, 2, 4, 5], [1, 1, 1, 2, 9], [1, 1, 1, 3, 3, 5], [1, 1, 1, 3, 4, 4], [1, 1, 1, 3, 8], [1, 1, 1, 4, 7], [1, 1, 1, 5, 6], [1, 1, 1, 11], [1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 2, 2, 2, 2, 4], [1, 1, 2, 2, 2, 3, 3], [1, 1, 2, 2, 2, 6], [1, 1, 2, 2, 3, 5], [1, 1, 2, 2, 4, 4], [1, 1, 2, 2, 8], [1, 1, 2, 3, 3, 4], [1, 1, 2, 3, 7], [1, 1, 2, 4, 6], [1, 1, 2, 5, 5], [1, 1, 2, 10], [1, 1, 3, 3, 3, 3], [1, 1, 3, 3, 6], [1, 1, 3, 4, 5], [1, 1, 3, 9], [1, 1, 4, 4, 4], [1, 1, 4, 8], [1, 1, 5, 7], [1, 1, 6, 6], [1, 1, 12], [1, 2, 2, 2, 2, 2, 3], [1, 2, 2, 2, 2, 5], [1, 2, 2, 2, 3, 4], [1, 2, 2, 2, 7], [1, 2, 2, 3, 3, 3], [1, 2, 2, 3, 6], [1, 2, 2, 4, 5], [1, 2, 2, 9], [1, 2, 3, 3, 5], [1, 2, 3, 4, 4], [1, 2, 3, 8], [1, 2, 4, 7], [1, 2, 5, 6], [1, 2, 11], [1, 3, 3, 3, 4], [1, 3, 3, 7], [1, 3, 4, 6], [1, 3, 5, 5], [1, 3, 10], [1, 4, 4, 5], [1, 4, 9], [1, 5, 8], [1, 6, 7], [1, 13], [2, 2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 2, 4], [2, 2, 2, 2, 3, 3], [2, 2, 2, 2, 6], [2, 2, 2, 3, 5], [2, 2, 2, 4, 4], [2, 2, 2, 8], [2, 2, 3, 3, 4], [2, 2, 3, 7], [2, 2, 4, 6], [2, 2, 5, 5], [2, 2, 10], [2, 3, 3, 3, 3], [2, 3, 3, 6], [2, 3, 4, 5], [2, 3, 9], [2, 4, 4, 4], [2, 4, 8], [2, 5, 7], [2, 6, 6], [2, 12], [3, 3, 3, 5], [3, 3, 4, 4], [3, 3, 8], [3, 4, 7], [3, 5, 6], [3, 11], [4, 4, 6], [4, 5, 5], [4, 10], [5, 9], [6, 8], [7, 7], [14]]
	if n == 15:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 11], [1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 2, 2, 8], [1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 2, 3, 7], [1, 1, 1, 2, 4, 6], [1, 1, 1, 2, 5, 5], [1, 1, 1, 2, 10], [1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 3, 3, 6], [1, 1, 1, 3, 4, 5], [1, 1, 1, 3, 9], [1, 1, 1, 4, 4, 4], [1, 1, 1, 4, 8], [1, 1, 1, 5, 7], [1, 1, 1, 6, 6], [1, 1, 1, 12], [1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 2, 2, 2, 2, 5], [1, 1, 2, 2, 2, 3, 4], [1, 1, 2, 2, 2, 7], [1, 1, 2, 2, 3, 3, 3], [1, 1, 2, 2, 3, 6], [1, 1, 2, 2, 4, 5], [1, 1, 2, 2, 9], [1, 1, 2, 3, 3, 5], [1, 1, 2, 3, 4, 4], [1, 1, 2, 3, 8], [1, 1, 2, 4, 7], [1, 1, 2, 5, 6], [1, 1, 2, 11], [1, 1, 3, 3, 3, 4], [1, 1, 3, 3, 7], [1, 1, 3, 4, 6], [1, 1, 3, 5, 5], [1, 1, 3, 10], [1, 1, 4, 4, 5], [1, 1, 4, 9], [1, 1, 5, 8], [1, 1, 6, 7], [1, 1, 13], [1, 2, 2, 2, 2, 2, 2, 2], [1, 2, 2, 2, 2, 2, 4], [1, 2, 2, 2, 2, 3, 3], [1, 2, 2, 2, 2, 6], [1, 2, 2, 2, 3, 5], [1, 2, 2, 2, 4, 4], [1, 2, 2, 2, 8], [1, 2, 2, 3, 3, 4], [1, 2, 2, 3, 7], [1, 2, 2, 4, 6], [1, 2, 2, 5, 5], [1, 2, 2, 10], [1, 2, 3, 3, 3, 3], [1, 2, 3, 3, 6], [1, 2, 3, 4, 5], [1, 2, 3, 9], [1, 2, 4, 4, 4], [1, 2, 4, 8], [1, 2, 5, 7], [1, 2, 6, 6], [1, 2, 12], [1, 3, 3, 3, 5], [1, 3, 3, 4, 4], [1, 3, 3, 8], [1, 3, 4, 7], [1, 3, 5, 6], [1, 3, 11], [1, 4, 4, 6], [1, 4, 5, 5], [1, 4, 10], [1, 5, 9], [1, 6, 8], [1, 7, 7], [1, 14], [2, 2, 2, 2, 2, 2, 3], [2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 3, 4], [2, 2, 2, 2, 7], [2, 2, 2, 3, 3, 3], [2, 2, 2, 3, 6], [2, 2, 2, 4, 5], [2, 2, 2, 9], [2, 2, 3, 3, 5], [2, 2, 3, 4, 4], [2, 2, 3, 8], [2, 2, 4, 7], [2, 2, 5, 6], [2, 2, 11], [2, 3, 3, 3, 4], [2, 3, 3, 7], [2, 3, 4, 6], [2, 3, 5, 5], [2, 3, 10], [2, 4, 4, 5], [2, 4, 9], [2, 5, 8], [2, 6, 7], [2, 13], [3, 3, 3, 3, 3], [3, 3, 3, 6], [3, 3, 4, 5], [3, 3, 9], [3, 4, 4, 4], [3, 4, 8], [3, 5, 7], [3, 6, 6], [3, 12], [4, 4, 7], [4, 5, 6], [4, 11], [5, 5, 5], [5, 10], [6, 9], [7, 8], [15]]
	if n == 16:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 1, 11], [1, 1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 1, 2, 2, 8], [1, 1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 1, 2, 3, 7], [1, 1, 1, 1, 2, 4, 6], [1, 1, 1, 1, 2, 5, 5], [1, 1, 1, 1, 2, 10], [1, 1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 1, 3, 3, 6], [1, 1, 1, 1, 3, 4, 5], [1, 1, 1, 1, 3, 9], [1, 1, 1, 1, 4, 4, 4], [1, 1, 1, 1, 4, 8], [1, 1, 1, 1, 5, 7], [1, 1, 1, 1, 6, 6], [1, 1, 1, 1, 12], [1, 1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 1, 2, 2, 2, 2, 5], [1, 1, 1, 2, 2, 2, 3, 4], [1, 1, 1, 2, 2, 2, 7], [1, 1, 1, 2, 2, 3, 3, 3], [1, 1, 1, 2, 2, 3, 6], [1, 1, 1, 2, 2, 4, 5], [1, 1, 1, 2, 2, 9], [1, 1, 1, 2, 3, 3, 5], [1, 1, 1, 2, 3, 4, 4], [1, 1, 1, 2, 3, 8], [1, 1, 1, 2, 4, 7], [1, 1, 1, 2, 5, 6], [1, 1, 1, 2, 11], [1, 1, 1, 3, 3, 3, 4], [1, 1, 1, 3, 3, 7], [1, 1, 1, 3, 4, 6], [1, 1, 1, 3, 5, 5], [1, 1, 1, 3, 10], [1, 1, 1, 4, 4, 5], [1, 1, 1, 4, 9], [1, 1, 1, 5, 8], [1, 1, 1, 6, 7], [1, 1, 1, 13], [1, 1, 2, 2, 2, 2, 2, 2, 2], [1, 1, 2, 2, 2, 2, 2, 4], [1, 1, 2, 2, 2, 2, 3, 3], [1, 1, 2, 2, 2, 2, 6], [1, 1, 2, 2, 2, 3, 5], [1, 1, 2, 2, 2, 4, 4], [1, 1, 2, 2, 2, 8], [1, 1, 2, 2, 3, 3, 4], [1, 1, 2, 2, 3, 7], [1, 1, 2, 2, 4, 6], [1, 1, 2, 2, 5, 5], [1, 1, 2, 2, 10], [1, 1, 2, 3, 3, 3, 3], [1, 1, 2, 3, 3, 6], [1, 1, 2, 3, 4, 5], [1, 1, 2, 3, 9], [1, 1, 2, 4, 4, 4], [1, 1, 2, 4, 8], [1, 1, 2, 5, 7], [1, 1, 2, 6, 6], [1, 1, 2, 12], [1, 1, 3, 3, 3, 5], [1, 1, 3, 3, 4, 4], [1, 1, 3, 3, 8], [1, 1, 3, 4, 7], [1, 1, 3, 5, 6], [1, 1, 3, 11], [1, 1, 4, 4, 6], [1, 1, 4, 5, 5], [1, 1, 4, 10], [1, 1, 5, 9], [1, 1, 6, 8], [1, 1, 7, 7], [1, 1, 14], [1, 2, 2, 2, 2, 2, 2, 3], [1, 2, 2, 2, 2, 2, 5], [1, 2, 2, 2, 2, 3, 4], [1, 2, 2, 2, 2, 7], [1, 2, 2, 2, 3, 3, 3], [1, 2, 2, 2, 3, 6], [1, 2, 2, 2, 4, 5], [1, 2, 2, 2, 9], [1, 2, 2, 3, 3, 5], [1, 2, 2, 3, 4, 4], [1, 2, 2, 3, 8], [1, 2, 2, 4, 7], [1, 2, 2, 5, 6], [1, 2, 2, 11], [1, 2, 3, 3, 3, 4], [1, 2, 3, 3, 7], [1, 2, 3, 4, 6], [1, 2, 3, 5, 5], [1, 2, 3, 10], [1, 2, 4, 4, 5], [1, 2, 4, 9], [1, 2, 5, 8], [1, 2, 6, 7], [1, 2, 13], [1, 3, 3, 3, 3, 3], [1, 3, 3, 3, 6], [1, 3, 3, 4, 5], [1, 3, 3, 9], [1, 3, 4, 4, 4], [1, 3, 4, 8], [1, 3, 5, 7], [1, 3, 6, 6], [1, 3, 12], [1, 4, 4, 7], [1, 4, 5, 6], [1, 4, 11], [1, 5, 5, 5], [1, 5, 10], [1, 6, 9], [1, 7, 8], [1, 15], [2, 2, 2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 2, 2, 4], [2, 2, 2, 2, 2, 3, 3], [2, 2, 2, 2, 2, 6], [2, 2, 2, 2, 3, 5], [2, 2, 2, 2, 4, 4], [2, 2, 2, 2, 8], [2, 2, 2, 3, 3, 4], [2, 2, 2, 3, 7], [2, 2, 2, 4, 6], [2, 2, 2, 5, 5], [2, 2, 2, 10], [2, 2, 3, 3, 3, 3], [2, 2, 3, 3, 6], [2, 2, 3, 4, 5], [2, 2, 3, 9], [2, 2, 4, 4, 4], [2, 2, 4, 8], [2, 2, 5, 7], [2, 2, 6, 6], [2, 2, 12], [2, 3, 3, 3, 5], [2, 3, 3, 4, 4], [2, 3, 3, 8], [2, 3, 4, 7], [2, 3, 5, 6], [2, 3, 11], [2, 4, 4, 6], [2, 4, 5, 5], [2, 4, 10], [2, 5, 9], [2, 6, 8], [2, 7, 7], [2, 14], [3, 3, 3, 3, 4], [3, 3, 3, 7], [3, 3, 4, 6], [3, 3, 5, 5], [3, 3, 10], [3, 4, 4, 5], [3, 4, 9], [3, 5, 8], [3, 6, 7], [3, 13], [4, 4, 4, 4], [4, 4, 8], [4, 5, 7], [4, 6, 6], [4, 12], [5, 5, 6], [5, 11], [6, 10], [7, 9], [8, 8], [16]]
	if n == 17:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 1, 1, 11], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 1, 1, 2, 2, 8], [1, 1, 1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 1, 1, 2, 3, 7], [1, 1, 1, 1, 1, 2, 4, 6], [1, 1, 1, 1, 1, 2, 5, 5], [1, 1, 1, 1, 1, 2, 10], [1, 1, 1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 1, 1, 3, 3, 6], [1, 1, 1, 1, 1, 3, 4, 5], [1, 1, 1, 1, 1, 3, 9], [1, 1, 1, 1, 1, 4, 4, 4], [1, 1, 1, 1, 1, 4, 8], [1, 1, 1, 1, 1, 5, 7], [1, 1, 1, 1, 1, 6, 6], [1, 1, 1, 1, 1, 12], [1, 1, 1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 1, 1, 2, 2, 2, 2, 5], [1, 1, 1, 1, 2, 2, 2, 3, 4], [1, 1, 1, 1, 2, 2, 2, 7], [1, 1, 1, 1, 2, 2, 3, 3, 3], [1, 1, 1, 1, 2, 2, 3, 6], [1, 1, 1, 1, 2, 2, 4, 5], [1, 1, 1, 1, 2, 2, 9], [1, 1, 1, 1, 2, 3, 3, 5], [1, 1, 1, 1, 2, 3, 4, 4], [1, 1, 1, 1, 2, 3, 8], [1, 1, 1, 1, 2, 4, 7], [1, 1, 1, 1, 2, 5, 6], [1, 1, 1, 1, 2, 11], [1, 1, 1, 1, 3, 3, 3, 4], [1, 1, 1, 1, 3, 3, 7], [1, 1, 1, 1, 3, 4, 6], [1, 1, 1, 1, 3, 5, 5], [1, 1, 1, 1, 3, 10], [1, 1, 1, 1, 4, 4, 5], [1, 1, 1, 1, 4, 9], [1, 1, 1, 1, 5, 8], [1, 1, 1, 1, 6, 7], [1, 1, 1, 1, 13], [1, 1, 1, 2, 2, 2, 2, 2, 2, 2], [1, 1, 1, 2, 2, 2, 2, 2, 4], [1, 1, 1, 2, 2, 2, 2, 3, 3], [1, 1, 1, 2, 2, 2, 2, 6], [1, 1, 1, 2, 2, 2, 3, 5], [1, 1, 1, 2, 2, 2, 4, 4], [1, 1, 1, 2, 2, 2, 8], [1, 1, 1, 2, 2, 3, 3, 4], [1, 1, 1, 2, 2, 3, 7], [1, 1, 1, 2, 2, 4, 6], [1, 1, 1, 2, 2, 5, 5], [1, 1, 1, 2, 2, 10], [1, 1, 1, 2, 3, 3, 3, 3], [1, 1, 1, 2, 3, 3, 6], [1, 1, 1, 2, 3, 4, 5], [1, 1, 1, 2, 3, 9], [1, 1, 1, 2, 4, 4, 4], [1, 1, 1, 2, 4, 8], [1, 1, 1, 2, 5, 7], [1, 1, 1, 2, 6, 6], [1, 1, 1, 2, 12], [1, 1, 1, 3, 3, 3, 5], [1, 1, 1, 3, 3, 4, 4], [1, 1, 1, 3, 3, 8], [1, 1, 1, 3, 4, 7], [1, 1, 1, 3, 5, 6], [1, 1, 1, 3, 11], [1, 1, 1, 4, 4, 6], [1, 1, 1, 4, 5, 5], [1, 1, 1, 4, 10], [1, 1, 1, 5, 9], [1, 1, 1, 6, 8], [1, 1, 1, 7, 7], [1, 1, 1, 14], [1, 1, 2, 2, 2, 2, 2, 2, 3], [1, 1, 2, 2, 2, 2, 2, 5], [1, 1, 2, 2, 2, 2, 3, 4], [1, 1, 2, 2, 2, 2, 7], [1, 1, 2, 2, 2, 3, 3, 3], [1, 1, 2, 2, 2, 3, 6], [1, 1, 2, 2, 2, 4, 5], [1, 1, 2, 2, 2, 9], [1, 1, 2, 2, 3, 3, 5], [1, 1, 2, 2, 3, 4, 4], [1, 1, 2, 2, 3, 8], [1, 1, 2, 2, 4, 7], [1, 1, 2, 2, 5, 6], [1, 1, 2, 2, 11], [1, 1, 2, 3, 3, 3, 4], [1, 1, 2, 3, 3, 7], [1, 1, 2, 3, 4, 6], [1, 1, 2, 3, 5, 5], [1, 1, 2, 3, 10], [1, 1, 2, 4, 4, 5], [1, 1, 2, 4, 9], [1, 1, 2, 5, 8], [1, 1, 2, 6, 7], [1, 1, 2, 13], [1, 1, 3, 3, 3, 3, 3], [1, 1, 3, 3, 3, 6], [1, 1, 3, 3, 4, 5], [1, 1, 3, 3, 9], [1, 1, 3, 4, 4, 4], [1, 1, 3, 4, 8], [1, 1, 3, 5, 7], [1, 1, 3, 6, 6], [1, 1, 3, 12], [1, 1, 4, 4, 7], [1, 1, 4, 5, 6], [1, 1, 4, 11], [1, 1, 5, 5, 5], [1, 1, 5, 10], [1, 1, 6, 9], [1, 1, 7, 8], [1, 1, 15], [1, 2, 2, 2, 2, 2, 2, 2, 2], [1, 2, 2, 2, 2, 2, 2, 4], [1, 2, 2, 2, 2, 2, 3, 3], [1, 2, 2, 2, 2, 2, 6], [1, 2, 2, 2, 2, 3, 5], [1, 2, 2, 2, 2, 4, 4], [1, 2, 2, 2, 2, 8], [1, 2, 2, 2, 3, 3, 4], [1, 2, 2, 2, 3, 7], [1, 2, 2, 2, 4, 6], [1, 2, 2, 2, 5, 5], [1, 2, 2, 2, 10], [1, 2, 2, 3, 3, 3, 3], [1, 2, 2, 3, 3, 6], [1, 2, 2, 3, 4, 5], [1, 2, 2, 3, 9], [1, 2, 2, 4, 4, 4], [1, 2, 2, 4, 8], [1, 2, 2, 5, 7], [1, 2, 2, 6, 6], [1, 2, 2, 12], [1, 2, 3, 3, 3, 5], [1, 2, 3, 3, 4, 4], [1, 2, 3, 3, 8], [1, 2, 3, 4, 7], [1, 2, 3, 5, 6], [1, 2, 3, 11], [1, 2, 4, 4, 6], [1, 2, 4, 5, 5], [1, 2, 4, 10], [1, 2, 5, 9], [1, 2, 6, 8], [1, 2, 7, 7], [1, 2, 14], [1, 3, 3, 3, 3, 4], [1, 3, 3, 3, 7], [1, 3, 3, 4, 6], [1, 3, 3, 5, 5], [1, 3, 3, 10], [1, 3, 4, 4, 5], [1, 3, 4, 9], [1, 3, 5, 8], [1, 3, 6, 7], [1, 3, 13], [1, 4, 4, 4, 4], [1, 4, 4, 8], [1, 4, 5, 7], [1, 4, 6, 6], [1, 4, 12], [1, 5, 5, 6], [1, 5, 11], [1, 6, 10], [1, 7, 9], [1, 8, 8], [1, 16], [2, 2, 2, 2, 2, 2, 2, 3], [2, 2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 2, 3, 4], [2, 2, 2, 2, 2, 7], [2, 2, 2, 2, 3, 3, 3], [2, 2, 2, 2, 3, 6], [2, 2, 2, 2, 4, 5], [2, 2, 2, 2, 9], [2, 2, 2, 3, 3, 5], [2, 2, 2, 3, 4, 4], [2, 2, 2, 3, 8], [2, 2, 2, 4, 7], [2, 2, 2, 5, 6], [2, 2, 2, 11], [2, 2, 3, 3, 3, 4], [2, 2, 3, 3, 7], [2, 2, 3, 4, 6], [2, 2, 3, 5, 5], [2, 2, 3, 10], [2, 2, 4, 4, 5], [2, 2, 4, 9], [2, 2, 5, 8], [2, 2, 6, 7], [2, 2, 13], [2, 3, 3, 3, 3, 3], [2, 3, 3, 3, 6], [2, 3, 3, 4, 5], [2, 3, 3, 9], [2, 3, 4, 4, 4], [2, 3, 4, 8], [2, 3, 5, 7], [2, 3, 6, 6], [2, 3, 12], [2, 4, 4, 7], [2, 4, 5, 6], [2, 4, 11], [2, 5, 5, 5], [2, 5, 10], [2, 6, 9], [2, 7, 8], [2, 15], [3, 3, 3, 3, 5], [3, 3, 3, 4, 4], [3, 3, 3, 8], [3, 3, 4, 7], [3, 3, 5, 6], [3, 3, 11], [3, 4, 4, 6], [3, 4, 5, 5], [3, 4, 10], [3, 5, 9], [3, 6, 8], [3, 7, 7], [3, 14], [4, 4, 4, 5], [4, 4, 9], [4, 5, 8], [4, 6, 7], [4, 13], [5, 5, 7], [5, 6, 6], [5, 12], [6, 11], [7, 10], [8, 9], [17]]
	if n == 18:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 1, 1, 1, 11], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 1, 1, 1, 2, 2, 8], [1, 1, 1, 1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 1, 1, 1, 2, 3, 7], [1, 1, 1, 1, 1, 1, 2, 4, 6], [1, 1, 1, 1, 1, 1, 2, 5, 5], [1, 1, 1, 1, 1, 1, 2, 10], [1, 1, 1, 1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 1, 1, 1, 3, 3, 6], [1, 1, 1, 1, 1, 1, 3, 4, 5], [1, 1, 1, 1, 1, 1, 3, 9], [1, 1, 1, 1, 1, 1, 4, 4, 4], [1, 1, 1, 1, 1, 1, 4, 8], [1, 1, 1, 1, 1, 1, 5, 7], [1, 1, 1, 1, 1, 1, 6, 6], [1, 1, 1, 1, 1, 1, 12], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 2, 2, 2, 2, 5], [1, 1, 1, 1, 1, 2, 2, 2, 3, 4], [1, 1, 1, 1, 1, 2, 2, 2, 7], [1, 1, 1, 1, 1, 2, 2, 3, 3, 3], [1, 1, 1, 1, 1, 2, 2, 3, 6], [1, 1, 1, 1, 1, 2, 2, 4, 5], [1, 1, 1, 1, 1, 2, 2, 9], [1, 1, 1, 1, 1, 2, 3, 3, 5], [1, 1, 1, 1, 1, 2, 3, 4, 4], [1, 1, 1, 1, 1, 2, 3, 8], [1, 1, 1, 1, 1, 2, 4, 7], [1, 1, 1, 1, 1, 2, 5, 6], [1, 1, 1, 1, 1, 2, 11], [1, 1, 1, 1, 1, 3, 3, 3, 4], [1, 1, 1, 1, 1, 3, 3, 7], [1, 1, 1, 1, 1, 3, 4, 6], [1, 1, 1, 1, 1, 3, 5, 5], [1, 1, 1, 1, 1, 3, 10], [1, 1, 1, 1, 1, 4, 4, 5], [1, 1, 1, 1, 1, 4, 9], [1, 1, 1, 1, 1, 5, 8], [1, 1, 1, 1, 1, 6, 7], [1, 1, 1, 1, 1, 13], [1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 2, 2, 2, 2, 2, 4], [1, 1, 1, 1, 2, 2, 2, 2, 3, 3], [1, 1, 1, 1, 2, 2, 2, 2, 6], [1, 1, 1, 1, 2, 2, 2, 3, 5], [1, 1, 1, 1, 2, 2, 2, 4, 4], [1, 1, 1, 1, 2, 2, 2, 8], [1, 1, 1, 1, 2, 2, 3, 3, 4], [1, 1, 1, 1, 2, 2, 3, 7], [1, 1, 1, 1, 2, 2, 4, 6], [1, 1, 1, 1, 2, 2, 5, 5], [1, 1, 1, 1, 2, 2, 10], [1, 1, 1, 1, 2, 3, 3, 3, 3], [1, 1, 1, 1, 2, 3, 3, 6], [1, 1, 1, 1, 2, 3, 4, 5], [1, 1, 1, 1, 2, 3, 9], [1, 1, 1, 1, 2, 4, 4, 4], [1, 1, 1, 1, 2, 4, 8], [1, 1, 1, 1, 2, 5, 7], [1, 1, 1, 1, 2, 6, 6], [1, 1, 1, 1, 2, 12], [1, 1, 1, 1, 3, 3, 3, 5], [1, 1, 1, 1, 3, 3, 4, 4], [1, 1, 1, 1, 3, 3, 8], [1, 1, 1, 1, 3, 4, 7], [1, 1, 1, 1, 3, 5, 6], [1, 1, 1, 1, 3, 11], [1, 1, 1, 1, 4, 4, 6], [1, 1, 1, 1, 4, 5, 5], [1, 1, 1, 1, 4, 10], [1, 1, 1, 1, 5, 9], [1, 1, 1, 1, 6, 8], [1, 1, 1, 1, 7, 7], [1, 1, 1, 1, 14], [1, 1, 1, 2, 2, 2, 2, 2, 2, 3], [1, 1, 1, 2, 2, 2, 2, 2, 5], [1, 1, 1, 2, 2, 2, 2, 3, 4], [1, 1, 1, 2, 2, 2, 2, 7], [1, 1, 1, 2, 2, 2, 3, 3, 3], [1, 1, 1, 2, 2, 2, 3, 6], [1, 1, 1, 2, 2, 2, 4, 5], [1, 1, 1, 2, 2, 2, 9], [1, 1, 1, 2, 2, 3, 3, 5], [1, 1, 1, 2, 2, 3, 4, 4], [1, 1, 1, 2, 2, 3, 8], [1, 1, 1, 2, 2, 4, 7], [1, 1, 1, 2, 2, 5, 6], [1, 1, 1, 2, 2, 11], [1, 1, 1, 2, 3, 3, 3, 4], [1, 1, 1, 2, 3, 3, 7], [1, 1, 1, 2, 3, 4, 6], [1, 1, 1, 2, 3, 5, 5], [1, 1, 1, 2, 3, 10], [1, 1, 1, 2, 4, 4, 5], [1, 1, 1, 2, 4, 9], [1, 1, 1, 2, 5, 8], [1, 1, 1, 2, 6, 7], [1, 1, 1, 2, 13], [1, 1, 1, 3, 3, 3, 3, 3], [1, 1, 1, 3, 3, 3, 6], [1, 1, 1, 3, 3, 4, 5], [1, 1, 1, 3, 3, 9], [1, 1, 1, 3, 4, 4, 4], [1, 1, 1, 3, 4, 8], [1, 1, 1, 3, 5, 7], [1, 1, 1, 3, 6, 6], [1, 1, 1, 3, 12], [1, 1, 1, 4, 4, 7], [1, 1, 1, 4, 5, 6], [1, 1, 1, 4, 11], [1, 1, 1, 5, 5, 5], [1, 1, 1, 5, 10], [1, 1, 1, 6, 9], [1, 1, 1, 7, 8], [1, 1, 1, 15], [1, 1, 2, 2, 2, 2, 2, 2, 2, 2], [1, 1, 2, 2, 2, 2, 2, 2, 4], [1, 1, 2, 2, 2, 2, 2, 3, 3], [1, 1, 2, 2, 2, 2, 2, 6], [1, 1, 2, 2, 2, 2, 3, 5], [1, 1, 2, 2, 2, 2, 4, 4], [1, 1, 2, 2, 2, 2, 8], [1, 1, 2, 2, 2, 3, 3, 4], [1, 1, 2, 2, 2, 3, 7], [1, 1, 2, 2, 2, 4, 6], [1, 1, 2, 2, 2, 5, 5], [1, 1, 2, 2, 2, 10], [1, 1, 2, 2, 3, 3, 3, 3], [1, 1, 2, 2, 3, 3, 6], [1, 1, 2, 2, 3, 4, 5], [1, 1, 2, 2, 3, 9], [1, 1, 2, 2, 4, 4, 4], [1, 1, 2, 2, 4, 8], [1, 1, 2, 2, 5, 7], [1, 1, 2, 2, 6, 6], [1, 1, 2, 2, 12], [1, 1, 2, 3, 3, 3, 5], [1, 1, 2, 3, 3, 4, 4], [1, 1, 2, 3, 3, 8], [1, 1, 2, 3, 4, 7], [1, 1, 2, 3, 5, 6], [1, 1, 2, 3, 11], [1, 1, 2, 4, 4, 6], [1, 1, 2, 4, 5, 5], [1, 1, 2, 4, 10], [1, 1, 2, 5, 9], [1, 1, 2, 6, 8], [1, 1, 2, 7, 7], [1, 1, 2, 14], [1, 1, 3, 3, 3, 3, 4], [1, 1, 3, 3, 3, 7], [1, 1, 3, 3, 4, 6], [1, 1, 3, 3, 5, 5], [1, 1, 3, 3, 10], [1, 1, 3, 4, 4, 5], [1, 1, 3, 4, 9], [1, 1, 3, 5, 8], [1, 1, 3, 6, 7], [1, 1, 3, 13], [1, 1, 4, 4, 4, 4], [1, 1, 4, 4, 8], [1, 1, 4, 5, 7], [1, 1, 4, 6, 6], [1, 1, 4, 12], [1, 1, 5, 5, 6], [1, 1, 5, 11], [1, 1, 6, 10], [1, 1, 7, 9], [1, 1, 8, 8], [1, 1, 16], [1, 2, 2, 2, 2, 2, 2, 2, 3], [1, 2, 2, 2, 2, 2, 2, 5], [1, 2, 2, 2, 2, 2, 3, 4], [1, 2, 2, 2, 2, 2, 7], [1, 2, 2, 2, 2, 3, 3, 3], [1, 2, 2, 2, 2, 3, 6], [1, 2, 2, 2, 2, 4, 5], [1, 2, 2, 2, 2, 9], [1, 2, 2, 2, 3, 3, 5], [1, 2, 2, 2, 3, 4, 4], [1, 2, 2, 2, 3, 8], [1, 2, 2, 2, 4, 7], [1, 2, 2, 2, 5, 6], [1, 2, 2, 2, 11], [1, 2, 2, 3, 3, 3, 4], [1, 2, 2, 3, 3, 7], [1, 2, 2, 3, 4, 6], [1, 2, 2, 3, 5, 5], [1, 2, 2, 3, 10], [1, 2, 2, 4, 4, 5], [1, 2, 2, 4, 9], [1, 2, 2, 5, 8], [1, 2, 2, 6, 7], [1, 2, 2, 13], [1, 2, 3, 3, 3, 3, 3], [1, 2, 3, 3, 3, 6], [1, 2, 3, 3, 4, 5], [1, 2, 3, 3, 9], [1, 2, 3, 4, 4, 4], [1, 2, 3, 4, 8], [1, 2, 3, 5, 7], [1, 2, 3, 6, 6], [1, 2, 3, 12], [1, 2, 4, 4, 7], [1, 2, 4, 5, 6], [1, 2, 4, 11], [1, 2, 5, 5, 5], [1, 2, 5, 10], [1, 2, 6, 9], [1, 2, 7, 8], [1, 2, 15], [1, 3, 3, 3, 3, 5], [1, 3, 3, 3, 4, 4], [1, 3, 3, 3, 8], [1, 3, 3, 4, 7], [1, 3, 3, 5, 6], [1, 3, 3, 11], [1, 3, 4, 4, 6], [1, 3, 4, 5, 5], [1, 3, 4, 10], [1, 3, 5, 9], [1, 3, 6, 8], [1, 3, 7, 7], [1, 3, 14], [1, 4, 4, 4, 5], [1, 4, 4, 9], [1, 4, 5, 8], [1, 4, 6, 7], [1, 4, 13], [1, 5, 5, 7], [1, 5, 6, 6], [1, 5, 12], [1, 6, 11], [1, 7, 10], [1, 8, 9], [1, 17], [2, 2, 2, 2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 2, 2, 2, 4], [2, 2, 2, 2, 2, 2, 3, 3], [2, 2, 2, 2, 2, 2, 6], [2, 2, 2, 2, 2, 3, 5], [2, 2, 2, 2, 2, 4, 4], [2, 2, 2, 2, 2, 8], [2, 2, 2, 2, 3, 3, 4], [2, 2, 2, 2, 3, 7], [2, 2, 2, 2, 4, 6], [2, 2, 2, 2, 5, 5], [2, 2, 2, 2, 10], [2, 2, 2, 3, 3, 3, 3], [2, 2, 2, 3, 3, 6], [2, 2, 2, 3, 4, 5], [2, 2, 2, 3, 9], [2, 2, 2, 4, 4, 4], [2, 2, 2, 4, 8], [2, 2, 2, 5, 7], [2, 2, 2, 6, 6], [2, 2, 2, 12], [2, 2, 3, 3, 3, 5], [2, 2, 3, 3, 4, 4], [2, 2, 3, 3, 8], [2, 2, 3, 4, 7], [2, 2, 3, 5, 6], [2, 2, 3, 11], [2, 2, 4, 4, 6], [2, 2, 4, 5, 5], [2, 2, 4, 10], [2, 2, 5, 9], [2, 2, 6, 8], [2, 2, 7, 7], [2, 2, 14], [2, 3, 3, 3, 3, 4], [2, 3, 3, 3, 7], [2, 3, 3, 4, 6], [2, 3, 3, 5, 5], [2, 3, 3, 10], [2, 3, 4, 4, 5], [2, 3, 4, 9], [2, 3, 5, 8], [2, 3, 6, 7], [2, 3, 13], [2, 4, 4, 4, 4], [2, 4, 4, 8], [2, 4, 5, 7], [2, 4, 6, 6], [2, 4, 12], [2, 5, 5, 6], [2, 5, 11], [2, 6, 10], [2, 7, 9], [2, 8, 8], [2, 16], [3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 6], [3, 3, 3, 4, 5], [3, 3, 3, 9], [3, 3, 4, 4, 4], [3, 3, 4, 8], [3, 3, 5, 7], [3, 3, 6, 6], [3, 3, 12], [3, 4, 4, 7], [3, 4, 5, 6], [3, 4, 11], [3, 5, 5, 5], [3, 5, 10], [3, 6, 9], [3, 7, 8], [3, 15], [4, 4, 4, 6], [4, 4, 5, 5], [4, 4, 10], [4, 5, 9], [4, 6, 8], [4, 7, 7], [4, 14], [5, 5, 8], [5, 6, 7], [5, 13], [6, 6, 6], [6, 12], [7, 11], [8, 10], [9, 9], [18]]
	if n == 19:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 1, 1, 1, 1, 11], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 1, 1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 1, 1, 1, 1, 2, 2, 8], [1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 1, 1, 1, 1, 2, 3, 7], [1, 1, 1, 1, 1, 1, 1, 2, 4, 6], [1, 1, 1, 1, 1, 1, 1, 2, 5, 5], [1, 1, 1, 1, 1, 1, 1, 2, 10], [1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 3, 3, 6], [1, 1, 1, 1, 1, 1, 1, 3, 4, 5], [1, 1, 1, 1, 1, 1, 1, 3, 9], [1, 1, 1, 1, 1, 1, 1, 4, 4, 4], [1, 1, 1, 1, 1, 1, 1, 4, 8], [1, 1, 1, 1, 1, 1, 1, 5, 7], [1, 1, 1, 1, 1, 1, 1, 6, 6], [1, 1, 1, 1, 1, 1, 1, 12], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 5], [1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4], [1, 1, 1, 1, 1, 1, 2, 2, 2, 7], [1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3], [1, 1, 1, 1, 1, 1, 2, 2, 3, 6], [1, 1, 1, 1, 1, 1, 2, 2, 4, 5], [1, 1, 1, 1, 1, 1, 2, 2, 9], [1, 1, 1, 1, 1, 1, 2, 3, 3, 5], [1, 1, 1, 1, 1, 1, 2, 3, 4, 4], [1, 1, 1, 1, 1, 1, 2, 3, 8], [1, 1, 1, 1, 1, 1, 2, 4, 7], [1, 1, 1, 1, 1, 1, 2, 5, 6], [1, 1, 1, 1, 1, 1, 2, 11], [1, 1, 1, 1, 1, 1, 3, 3, 3, 4], [1, 1, 1, 1, 1, 1, 3, 3, 7], [1, 1, 1, 1, 1, 1, 3, 4, 6], [1, 1, 1, 1, 1, 1, 3, 5, 5], [1, 1, 1, 1, 1, 1, 3, 10], [1, 1, 1, 1, 1, 1, 4, 4, 5], [1, 1, 1, 1, 1, 1, 4, 9], [1, 1, 1, 1, 1, 1, 5, 8], [1, 1, 1, 1, 1, 1, 6, 7], [1, 1, 1, 1, 1, 1, 13], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4], [1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3], [1, 1, 1, 1, 1, 2, 2, 2, 2, 6], [1, 1, 1, 1, 1, 2, 2, 2, 3, 5], [1, 1, 1, 1, 1, 2, 2, 2, 4, 4], [1, 1, 1, 1, 1, 2, 2, 2, 8], [1, 1, 1, 1, 1, 2, 2, 3, 3, 4], [1, 1, 1, 1, 1, 2, 2, 3, 7], [1, 1, 1, 1, 1, 2, 2, 4, 6], [1, 1, 1, 1, 1, 2, 2, 5, 5], [1, 1, 1, 1, 1, 2, 2, 10], [1, 1, 1, 1, 1, 2, 3, 3, 3, 3], [1, 1, 1, 1, 1, 2, 3, 3, 6], [1, 1, 1, 1, 1, 2, 3, 4, 5], [1, 1, 1, 1, 1, 2, 3, 9], [1, 1, 1, 1, 1, 2, 4, 4, 4], [1, 1, 1, 1, 1, 2, 4, 8], [1, 1, 1, 1, 1, 2, 5, 7], [1, 1, 1, 1, 1, 2, 6, 6], [1, 1, 1, 1, 1, 2, 12], [1, 1, 1, 1, 1, 3, 3, 3, 5], [1, 1, 1, 1, 1, 3, 3, 4, 4], [1, 1, 1, 1, 1, 3, 3, 8], [1, 1, 1, 1, 1, 3, 4, 7], [1, 1, 1, 1, 1, 3, 5, 6], [1, 1, 1, 1, 1, 3, 11], [1, 1, 1, 1, 1, 4, 4, 6], [1, 1, 1, 1, 1, 4, 5, 5], [1, 1, 1, 1, 1, 4, 10], [1, 1, 1, 1, 1, 5, 9], [1, 1, 1, 1, 1, 6, 8], [1, 1, 1, 1, 1, 7, 7], [1, 1, 1, 1, 1, 14], [1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3], [1, 1, 1, 1, 2, 2, 2, 2, 2, 5], [1, 1, 1, 1, 2, 2, 2, 2, 3, 4], [1, 1, 1, 1, 2, 2, 2, 2, 7], [1, 1, 1, 1, 2, 2, 2, 3, 3, 3], [1, 1, 1, 1, 2, 2, 2, 3, 6], [1, 1, 1, 1, 2, 2, 2, 4, 5], [1, 1, 1, 1, 2, 2, 2, 9], [1, 1, 1, 1, 2, 2, 3, 3, 5], [1, 1, 1, 1, 2, 2, 3, 4, 4], [1, 1, 1, 1, 2, 2, 3, 8], [1, 1, 1, 1, 2, 2, 4, 7], [1, 1, 1, 1, 2, 2, 5, 6], [1, 1, 1, 1, 2, 2, 11], [1, 1, 1, 1, 2, 3, 3, 3, 4], [1, 1, 1, 1, 2, 3, 3, 7], [1, 1, 1, 1, 2, 3, 4, 6], [1, 1, 1, 1, 2, 3, 5, 5], [1, 1, 1, 1, 2, 3, 10], [1, 1, 1, 1, 2, 4, 4, 5], [1, 1, 1, 1, 2, 4, 9], [1, 1, 1, 1, 2, 5, 8], [1, 1, 1, 1, 2, 6, 7], [1, 1, 1, 1, 2, 13], [1, 1, 1, 1, 3, 3, 3, 3, 3], [1, 1, 1, 1, 3, 3, 3, 6], [1, 1, 1, 1, 3, 3, 4, 5], [1, 1, 1, 1, 3, 3, 9], [1, 1, 1, 1, 3, 4, 4, 4], [1, 1, 1, 1, 3, 4, 8], [1, 1, 1, 1, 3, 5, 7], [1, 1, 1, 1, 3, 6, 6], [1, 1, 1, 1, 3, 12], [1, 1, 1, 1, 4, 4, 7], [1, 1, 1, 1, 4, 5, 6], [1, 1, 1, 1, 4, 11], [1, 1, 1, 1, 5, 5, 5], [1, 1, 1, 1, 5, 10], [1, 1, 1, 1, 6, 9], [1, 1, 1, 1, 7, 8], [1, 1, 1, 1, 15], [1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2], [1, 1, 1, 2, 2, 2, 2, 2, 2, 4], [1, 1, 1, 2, 2, 2, 2, 2, 3, 3], [1, 1, 1, 2, 2, 2, 2, 2, 6], [1, 1, 1, 2, 2, 2, 2, 3, 5], [1, 1, 1, 2, 2, 2, 2, 4, 4], [1, 1, 1, 2, 2, 2, 2, 8], [1, 1, 1, 2, 2, 2, 3, 3, 4], [1, 1, 1, 2, 2, 2, 3, 7], [1, 1, 1, 2, 2, 2, 4, 6], [1, 1, 1, 2, 2, 2, 5, 5], [1, 1, 1, 2, 2, 2, 10], [1, 1, 1, 2, 2, 3, 3, 3, 3], [1, 1, 1, 2, 2, 3, 3, 6], [1, 1, 1, 2, 2, 3, 4, 5], [1, 1, 1, 2, 2, 3, 9], [1, 1, 1, 2, 2, 4, 4, 4], [1, 1, 1, 2, 2, 4, 8], [1, 1, 1, 2, 2, 5, 7], [1, 1, 1, 2, 2, 6, 6], [1, 1, 1, 2, 2, 12], [1, 1, 1, 2, 3, 3, 3, 5], [1, 1, 1, 2, 3, 3, 4, 4], [1, 1, 1, 2, 3, 3, 8], [1, 1, 1, 2, 3, 4, 7], [1, 1, 1, 2, 3, 5, 6], [1, 1, 1, 2, 3, 11], [1, 1, 1, 2, 4, 4, 6], [1, 1, 1, 2, 4, 5, 5], [1, 1, 1, 2, 4, 10], [1, 1, 1, 2, 5, 9], [1, 1, 1, 2, 6, 8], [1, 1, 1, 2, 7, 7], [1, 1, 1, 2, 14], [1, 1, 1, 3, 3, 3, 3, 4], [1, 1, 1, 3, 3, 3, 7], [1, 1, 1, 3, 3, 4, 6], [1, 1, 1, 3, 3, 5, 5], [1, 1, 1, 3, 3, 10], [1, 1, 1, 3, 4, 4, 5], [1, 1, 1, 3, 4, 9], [1, 1, 1, 3, 5, 8], [1, 1, 1, 3, 6, 7], [1, 1, 1, 3, 13], [1, 1, 1, 4, 4, 4, 4], [1, 1, 1, 4, 4, 8], [1, 1, 1, 4, 5, 7], [1, 1, 1, 4, 6, 6], [1, 1, 1, 4, 12], [1, 1, 1, 5, 5, 6], [1, 1, 1, 5, 11], [1, 1, 1, 6, 10], [1, 1, 1, 7, 9], [1, 1, 1, 8, 8], [1, 1, 1, 16], [1, 1, 2, 2, 2, 2, 2, 2, 2, 3], [1, 1, 2, 2, 2, 2, 2, 2, 5], [1, 1, 2, 2, 2, 2, 2, 3, 4], [1, 1, 2, 2, 2, 2, 2, 7], [1, 1, 2, 2, 2, 2, 3, 3, 3], [1, 1, 2, 2, 2, 2, 3, 6], [1, 1, 2, 2, 2, 2, 4, 5], [1, 1, 2, 2, 2, 2, 9], [1, 1, 2, 2, 2, 3, 3, 5], [1, 1, 2, 2, 2, 3, 4, 4], [1, 1, 2, 2, 2, 3, 8], [1, 1, 2, 2, 2, 4, 7], [1, 1, 2, 2, 2, 5, 6], [1, 1, 2, 2, 2, 11], [1, 1, 2, 2, 3, 3, 3, 4], [1, 1, 2, 2, 3, 3, 7], [1, 1, 2, 2, 3, 4, 6], [1, 1, 2, 2, 3, 5, 5], [1, 1, 2, 2, 3, 10], [1, 1, 2, 2, 4, 4, 5], [1, 1, 2, 2, 4, 9], [1, 1, 2, 2, 5, 8], [1, 1, 2, 2, 6, 7], [1, 1, 2, 2, 13], [1, 1, 2, 3, 3, 3, 3, 3], [1, 1, 2, 3, 3, 3, 6], [1, 1, 2, 3, 3, 4, 5], [1, 1, 2, 3, 3, 9], [1, 1, 2, 3, 4, 4, 4], [1, 1, 2, 3, 4, 8], [1, 1, 2, 3, 5, 7], [1, 1, 2, 3, 6, 6], [1, 1, 2, 3, 12], [1, 1, 2, 4, 4, 7], [1, 1, 2, 4, 5, 6], [1, 1, 2, 4, 11], [1, 1, 2, 5, 5, 5], [1, 1, 2, 5, 10], [1, 1, 2, 6, 9], [1, 1, 2, 7, 8], [1, 1, 2, 15], [1, 1, 3, 3, 3, 3, 5], [1, 1, 3, 3, 3, 4, 4], [1, 1, 3, 3, 3, 8], [1, 1, 3, 3, 4, 7], [1, 1, 3, 3, 5, 6], [1, 1, 3, 3, 11], [1, 1, 3, 4, 4, 6], [1, 1, 3, 4, 5, 5], [1, 1, 3, 4, 10], [1, 1, 3, 5, 9], [1, 1, 3, 6, 8], [1, 1, 3, 7, 7], [1, 1, 3, 14], [1, 1, 4, 4, 4, 5], [1, 1, 4, 4, 9], [1, 1, 4, 5, 8], [1, 1, 4, 6, 7], [1, 1, 4, 13], [1, 1, 5, 5, 7], [1, 1, 5, 6, 6], [1, 1, 5, 12], [1, 1, 6, 11], [1, 1, 7, 10], [1, 1, 8, 9], [1, 1, 17], [1, 2, 2, 2, 2, 2, 2, 2, 2, 2], [1, 2, 2, 2, 2, 2, 2, 2, 4], [1, 2, 2, 2, 2, 2, 2, 3, 3], [1, 2, 2, 2, 2, 2, 2, 6], [1, 2, 2, 2, 2, 2, 3, 5], [1, 2, 2, 2, 2, 2, 4, 4], [1, 2, 2, 2, 2, 2, 8], [1, 2, 2, 2, 2, 3, 3, 4], [1, 2, 2, 2, 2, 3, 7], [1, 2, 2, 2, 2, 4, 6], [1, 2, 2, 2, 2, 5, 5], [1, 2, 2, 2, 2, 10], [1, 2, 2, 2, 3, 3, 3, 3], [1, 2, 2, 2, 3, 3, 6], [1, 2, 2, 2, 3, 4, 5], [1, 2, 2, 2, 3, 9], [1, 2, 2, 2, 4, 4, 4], [1, 2, 2, 2, 4, 8], [1, 2, 2, 2, 5, 7], [1, 2, 2, 2, 6, 6], [1, 2, 2, 2, 12], [1, 2, 2, 3, 3, 3, 5], [1, 2, 2, 3, 3, 4, 4], [1, 2, 2, 3, 3, 8], [1, 2, 2, 3, 4, 7], [1, 2, 2, 3, 5, 6], [1, 2, 2, 3, 11], [1, 2, 2, 4, 4, 6], [1, 2, 2, 4, 5, 5], [1, 2, 2, 4, 10], [1, 2, 2, 5, 9], [1, 2, 2, 6, 8], [1, 2, 2, 7, 7], [1, 2, 2, 14], [1, 2, 3, 3, 3, 3, 4], [1, 2, 3, 3, 3, 7], [1, 2, 3, 3, 4, 6], [1, 2, 3, 3, 5, 5], [1, 2, 3, 3, 10], [1, 2, 3, 4, 4, 5], [1, 2, 3, 4, 9], [1, 2, 3, 5, 8], [1, 2, 3, 6, 7], [1, 2, 3, 13], [1, 2, 4, 4, 4, 4], [1, 2, 4, 4, 8], [1, 2, 4, 5, 7], [1, 2, 4, 6, 6], [1, 2, 4, 12], [1, 2, 5, 5, 6], [1, 2, 5, 11], [1, 2, 6, 10], [1, 2, 7, 9], [1, 2, 8, 8], [1, 2, 16], [1, 3, 3, 3, 3, 3, 3], [1, 3, 3, 3, 3, 6], [1, 3, 3, 3, 4, 5], [1, 3, 3, 3, 9], [1, 3, 3, 4, 4, 4], [1, 3, 3, 4, 8], [1, 3, 3, 5, 7], [1, 3, 3, 6, 6], [1, 3, 3, 12], [1, 3, 4, 4, 7], [1, 3, 4, 5, 6], [1, 3, 4, 11], [1, 3, 5, 5, 5], [1, 3, 5, 10], [1, 3, 6, 9], [1, 3, 7, 8], [1, 3, 15], [1, 4, 4, 4, 6], [1, 4, 4, 5, 5], [1, 4, 4, 10], [1, 4, 5, 9], [1, 4, 6, 8], [1, 4, 7, 7], [1, 4, 14], [1, 5, 5, 8], [1, 5, 6, 7], [1, 5, 13], [1, 6, 6, 6], [1, 6, 12], [1, 7, 11], [1, 8, 10], [1, 9, 9], [1, 18], [2, 2, 2, 2, 2, 2, 2, 2, 3], [2, 2, 2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 2, 2, 3, 4], [2, 2, 2, 2, 2, 2, 7], [2, 2, 2, 2, 2, 3, 3, 3], [2, 2, 2, 2, 2, 3, 6], [2, 2, 2, 2, 2, 4, 5], [2, 2, 2, 2, 2, 9], [2, 2, 2, 2, 3, 3, 5], [2, 2, 2, 2, 3, 4, 4], [2, 2, 2, 2, 3, 8], [2, 2, 2, 2, 4, 7], [2, 2, 2, 2, 5, 6], [2, 2, 2, 2, 11], [2, 2, 2, 3, 3, 3, 4], [2, 2, 2, 3, 3, 7], [2, 2, 2, 3, 4, 6], [2, 2, 2, 3, 5, 5], [2, 2, 2, 3, 10], [2, 2, 2, 4, 4, 5], [2, 2, 2, 4, 9], [2, 2, 2, 5, 8], [2, 2, 2, 6, 7], [2, 2, 2, 13], [2, 2, 3, 3, 3, 3, 3], [2, 2, 3, 3, 3, 6], [2, 2, 3, 3, 4, 5], [2, 2, 3, 3, 9], [2, 2, 3, 4, 4, 4], [2, 2, 3, 4, 8], [2, 2, 3, 5, 7], [2, 2, 3, 6, 6], [2, 2, 3, 12], [2, 2, 4, 4, 7], [2, 2, 4, 5, 6], [2, 2, 4, 11], [2, 2, 5, 5, 5], [2, 2, 5, 10], [2, 2, 6, 9], [2, 2, 7, 8], [2, 2, 15], [2, 3, 3, 3, 3, 5], [2, 3, 3, 3, 4, 4], [2, 3, 3, 3, 8], [2, 3, 3, 4, 7], [2, 3, 3, 5, 6], [2, 3, 3, 11], [2, 3, 4, 4, 6], [2, 3, 4, 5, 5], [2, 3, 4, 10], [2, 3, 5, 9], [2, 3, 6, 8], [2, 3, 7, 7], [2, 3, 14], [2, 4, 4, 4, 5], [2, 4, 4, 9], [2, 4, 5, 8], [2, 4, 6, 7], [2, 4, 13], [2, 5, 5, 7], [2, 5, 6, 6], [2, 5, 12], [2, 6, 11], [2, 7, 10], [2, 8, 9], [2, 17], [3, 3, 3, 3, 3, 4], [3, 3, 3, 3, 7], [3, 3, 3, 4, 6], [3, 3, 3, 5, 5], [3, 3, 3, 10], [3, 3, 4, 4, 5], [3, 3, 4, 9], [3, 3, 5, 8], [3, 3, 6, 7], [3, 3, 13], [3, 4, 4, 4, 4], [3, 4, 4, 8], [3, 4, 5, 7], [3, 4, 6, 6], [3, 4, 12], [3, 5, 5, 6], [3, 5, 11], [3, 6, 10], [3, 7, 9], [3, 8, 8], [3, 16], [4, 4, 4, 7], [4, 4, 5, 6], [4, 4, 11], [4, 5, 5, 5], [4, 5, 10], [4, 6, 9], [4, 7, 8], [4, 15], [5, 5, 9], [5, 6, 8], [5, 7, 7], [5, 14], [6, 6, 7], [6, 13], [7, 12], [8, 11], [9, 10], [19]]
	if n == 20:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 11], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 8], [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 7], [1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 5], [1, 1, 1, 1, 1, 1, 1, 1, 2, 10], [1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 6], [1, 1, 1, 1, 1, 1, 1, 1, 3, 4, 5], [1, 1, 1, 1, 1, 1, 1, 1, 3, 9], [1, 1, 1, 1, 1, 1, 1, 1, 4, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 4, 8], [1, 1, 1, 1, 1, 1, 1, 1, 5, 7], [1, 1, 1, 1, 1, 1, 1, 1, 6, 6], [1, 1, 1, 1, 1, 1, 1, 1, 12], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 5], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 7], [1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 6], [1, 1, 1, 1, 1, 1, 1, 2, 2, 4, 5], [1, 1, 1, 1, 1, 1, 1, 2, 2, 9], [1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 5], [1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 4], [1, 1, 1, 1, 1, 1, 1, 2, 3, 8], [1, 1, 1, 1, 1, 1, 1, 2, 4, 7], [1, 1, 1, 1, 1, 1, 1, 2, 5, 6], [1, 1, 1, 1, 1, 1, 1, 2, 11], [1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 4], [1, 1, 1, 1, 1, 1, 1, 3, 3, 7], [1, 1, 1, 1, 1, 1, 1, 3, 4, 6], [1, 1, 1, 1, 1, 1, 1, 3, 5, 5], [1, 1, 1, 1, 1, 1, 1, 3, 10], [1, 1, 1, 1, 1, 1, 1, 4, 4, 5], [1, 1, 1, 1, 1, 1, 1, 4, 9], [1, 1, 1, 1, 1, 1, 1, 5, 8], [1, 1, 1, 1, 1, 1, 1, 6, 7], [1, 1, 1, 1, 1, 1, 1, 13], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 6], [1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 5], [1, 1, 1, 1, 1, 1, 2, 2, 2, 4, 4], [1, 1, 1, 1, 1, 1, 2, 2, 2, 8], [1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4], [1, 1, 1, 1, 1, 1, 2, 2, 3, 7], [1, 1, 1, 1, 1, 1, 2, 2, 4, 6], [1, 1, 1, 1, 1, 1, 2, 2, 5, 5], [1, 1, 1, 1, 1, 1, 2, 2, 10], [1, 1, 1, 1, 1, 1, 2, 3, 3, 3, 3], [1, 1, 1, 1, 1, 1, 2, 3, 3, 6], [1, 1, 1, 1, 1, 1, 2, 3, 4, 5], [1, 1, 1, 1, 1, 1, 2, 3, 9], [1, 1, 1, 1, 1, 1, 2, 4, 4, 4], [1, 1, 1, 1, 1, 1, 2, 4, 8], [1, 1, 1, 1, 1, 1, 2, 5, 7], [1, 1, 1, 1, 1, 1, 2, 6, 6], [1, 1, 1, 1, 1, 1, 2, 12], [1, 1, 1, 1, 1, 1, 3, 3, 3, 5], [1, 1, 1, 1, 1, 1, 3, 3, 4, 4], [1, 1, 1, 1, 1, 1, 3, 3, 8], [1, 1, 1, 1, 1, 1, 3, 4, 7], [1, 1, 1, 1, 1, 1, 3, 5, 6], [1, 1, 1, 1, 1, 1, 3, 11], [1, 1, 1, 1, 1, 1, 4, 4, 6], [1, 1, 1, 1, 1, 1, 4, 5, 5], [1, 1, 1, 1, 1, 1, 4, 10], [1, 1, 1, 1, 1, 1, 5, 9], [1, 1, 1, 1, 1, 1, 6, 8], [1, 1, 1, 1, 1, 1, 7, 7], [1, 1, 1, 1, 1, 1, 14], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 5], [1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4], [1, 1, 1, 1, 1, 2, 2, 2, 2, 7], [1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3], [1, 1, 1, 1, 1, 2, 2, 2, 3, 6], [1, 1, 1, 1, 1, 2, 2, 2, 4, 5], [1, 1, 1, 1, 1, 2, 2, 2, 9], [1, 1, 1, 1, 1, 2, 2, 3, 3, 5], [1, 1, 1, 1, 1, 2, 2, 3, 4, 4], [1, 1, 1, 1, 1, 2, 2, 3, 8], [1, 1, 1, 1, 1, 2, 2, 4, 7], [1, 1, 1, 1, 1, 2, 2, 5, 6], [1, 1, 1, 1, 1, 2, 2, 11], [1, 1, 1, 1, 1, 2, 3, 3, 3, 4], [1, 1, 1, 1, 1, 2, 3, 3, 7], [1, 1, 1, 1, 1, 2, 3, 4, 6], [1, 1, 1, 1, 1, 2, 3, 5, 5], [1, 1, 1, 1, 1, 2, 3, 10], [1, 1, 1, 1, 1, 2, 4, 4, 5], [1, 1, 1, 1, 1, 2, 4, 9], [1, 1, 1, 1, 1, 2, 5, 8], [1, 1, 1, 1, 1, 2, 6, 7], [1, 1, 1, 1, 1, 2, 13], [1, 1, 1, 1, 1, 3, 3, 3, 3, 3], [1, 1, 1, 1, 1, 3, 3, 3, 6], [1, 1, 1, 1, 1, 3, 3, 4, 5], [1, 1, 1, 1, 1, 3, 3, 9], [1, 1, 1, 1, 1, 3, 4, 4, 4], [1, 1, 1, 1, 1, 3, 4, 8], [1, 1, 1, 1, 1, 3, 5, 7], [1, 1, 1, 1, 1, 3, 6, 6], [1, 1, 1, 1, 1, 3, 12], [1, 1, 1, 1, 1, 4, 4, 7], [1, 1, 1, 1, 1, 4, 5, 6], [1, 1, 1, 1, 1, 4, 11], [1, 1, 1, 1, 1, 5, 5, 5], [1, 1, 1, 1, 1, 5, 10], [1, 1, 1, 1, 1, 6, 9], [1, 1, 1, 1, 1, 7, 8], [1, 1, 1, 1, 1, 15], [1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 4], [1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3], [1, 1, 1, 1, 2, 2, 2, 2, 2, 6], [1, 1, 1, 1, 2, 2, 2, 2, 3, 5], [1, 1, 1, 1, 2, 2, 2, 2, 4, 4], [1, 1, 1, 1, 2, 2, 2, 2, 8], [1, 1, 1, 1, 2, 2, 2, 3, 3, 4], [1, 1, 1, 1, 2, 2, 2, 3, 7], [1, 1, 1, 1, 2, 2, 2, 4, 6], [1, 1, 1, 1, 2, 2, 2, 5, 5], [1, 1, 1, 1, 2, 2, 2, 10], [1, 1, 1, 1, 2, 2, 3, 3, 3, 3], [1, 1, 1, 1, 2, 2, 3, 3, 6], [1, 1, 1, 1, 2, 2, 3, 4, 5], [1, 1, 1, 1, 2, 2, 3, 9], [1, 1, 1, 1, 2, 2, 4, 4, 4], [1, 1, 1, 1, 2, 2, 4, 8], [1, 1, 1, 1, 2, 2, 5, 7], [1, 1, 1, 1, 2, 2, 6, 6], [1, 1, 1, 1, 2, 2, 12], [1, 1, 1, 1, 2, 3, 3, 3, 5], [1, 1, 1, 1, 2, 3, 3, 4, 4], [1, 1, 1, 1, 2, 3, 3, 8], [1, 1, 1, 1, 2, 3, 4, 7], [1, 1, 1, 1, 2, 3, 5, 6], [1, 1, 1, 1, 2, 3, 11], [1, 1, 1, 1, 2, 4, 4, 6], [1, 1, 1, 1, 2, 4, 5, 5], [1, 1, 1, 1, 2, 4, 10], [1, 1, 1, 1, 2, 5, 9], [1, 1, 1, 1, 2, 6, 8], [1, 1, 1, 1, 2, 7, 7], [1, 1, 1, 1, 2, 14], [1, 1, 1, 1, 3, 3, 3, 3, 4], [1, 1, 1, 1, 3, 3, 3, 7], [1, 1, 1, 1, 3, 3, 4, 6], [1, 1, 1, 1, 3, 3, 5, 5], [1, 1, 1, 1, 3, 3, 10], [1, 1, 1, 1, 3, 4, 4, 5], [1, 1, 1, 1, 3, 4, 9], [1, 1, 1, 1, 3, 5, 8], [1, 1, 1, 1, 3, 6, 7], [1, 1, 1, 1, 3, 13], [1, 1, 1, 1, 4, 4, 4, 4], [1, 1, 1, 1, 4, 4, 8], [1, 1, 1, 1, 4, 5, 7], [1, 1, 1, 1, 4, 6, 6], [1, 1, 1, 1, 4, 12], [1, 1, 1, 1, 5, 5, 6], [1, 1, 1, 1, 5, 11], [1, 1, 1, 1, 6, 10], [1, 1, 1, 1, 7, 9], [1, 1, 1, 1, 8, 8], [1, 1, 1, 1, 16], [1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3], [1, 1, 1, 2, 2, 2, 2, 2, 2, 5], [1, 1, 1, 2, 2, 2, 2, 2, 3, 4], [1, 1, 1, 2, 2, 2, 2, 2, 7], [1, 1, 1, 2, 2, 2, 2, 3, 3, 3], [1, 1, 1, 2, 2, 2, 2, 3, 6], [1, 1, 1, 2, 2, 2, 2, 4, 5], [1, 1, 1, 2, 2, 2, 2, 9], [1, 1, 1, 2, 2, 2, 3, 3, 5], [1, 1, 1, 2, 2, 2, 3, 4, 4], [1, 1, 1, 2, 2, 2, 3, 8], [1, 1, 1, 2, 2, 2, 4, 7], [1, 1, 1, 2, 2, 2, 5, 6], [1, 1, 1, 2, 2, 2, 11], [1, 1, 1, 2, 2, 3, 3, 3, 4], [1, 1, 1, 2, 2, 3, 3, 7], [1, 1, 1, 2, 2, 3, 4, 6], [1, 1, 1, 2, 2, 3, 5, 5], [1, 1, 1, 2, 2, 3, 10], [1, 1, 1, 2, 2, 4, 4, 5], [1, 1, 1, 2, 2, 4, 9], [1, 1, 1, 2, 2, 5, 8], [1, 1, 1, 2, 2, 6, 7], [1, 1, 1, 2, 2, 13], [1, 1, 1, 2, 3, 3, 3, 3, 3], [1, 1, 1, 2, 3, 3, 3, 6], [1, 1, 1, 2, 3, 3, 4, 5], [1, 1, 1, 2, 3, 3, 9], [1, 1, 1, 2, 3, 4, 4, 4], [1, 1, 1, 2, 3, 4, 8], [1, 1, 1, 2, 3, 5, 7], [1, 1, 1, 2, 3, 6, 6], [1, 1, 1, 2, 3, 12], [1, 1, 1, 2, 4, 4, 7], [1, 1, 1, 2, 4, 5, 6], [1, 1, 1, 2, 4, 11], [1, 1, 1, 2, 5, 5, 5], [1, 1, 1, 2, 5, 10], [1, 1, 1, 2, 6, 9], [1, 1, 1, 2, 7, 8], [1, 1, 1, 2, 15], [1, 1, 1, 3, 3, 3, 3, 5], [1, 1, 1, 3, 3, 3, 4, 4], [1, 1, 1, 3, 3, 3, 8], [1, 1, 1, 3, 3, 4, 7], [1, 1, 1, 3, 3, 5, 6], [1, 1, 1, 3, 3, 11], [1, 1, 1, 3, 4, 4, 6], [1, 1, 1, 3, 4, 5, 5], [1, 1, 1, 3, 4, 10], [1, 1, 1, 3, 5, 9], [1, 1, 1, 3, 6, 8], [1, 1, 1, 3, 7, 7], [1, 1, 1, 3, 14], [1, 1, 1, 4, 4, 4, 5], [1, 1, 1, 4, 4, 9], [1, 1, 1, 4, 5, 8], [1, 1, 1, 4, 6, 7], [1, 1, 1, 4, 13], [1, 1, 1, 5, 5, 7], [1, 1, 1, 5, 6, 6], [1, 1, 1, 5, 12], [1, 1, 1, 6, 11], [1, 1, 1, 7, 10], [1, 1, 1, 8, 9], [1, 1, 1, 17], [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2], [1, 1, 2, 2, 2, 2, 2, 2, 2, 4], [1, 1, 2, 2, 2, 2, 2, 2, 3, 3], [1, 1, 2, 2, 2, 2, 2, 2, 6], [1, 1, 2, 2, 2, 2, 2, 3, 5], [1, 1, 2, 2, 2, 2, 2, 4, 4], [1, 1, 2, 2, 2, 2, 2, 8], [1, 1, 2, 2, 2, 2, 3, 3, 4], [1, 1, 2, 2, 2, 2, 3, 7], [1, 1, 2, 2, 2, 2, 4, 6], [1, 1, 2, 2, 2, 2, 5, 5], [1, 1, 2, 2, 2, 2, 10], [1, 1, 2, 2, 2, 3, 3, 3, 3], [1, 1, 2, 2, 2, 3, 3, 6], [1, 1, 2, 2, 2, 3, 4, 5], [1, 1, 2, 2, 2, 3, 9], [1, 1, 2, 2, 2, 4, 4, 4], [1, 1, 2, 2, 2, 4, 8], [1, 1, 2, 2, 2, 5, 7], [1, 1, 2, 2, 2, 6, 6], [1, 1, 2, 2, 2, 12], [1, 1, 2, 2, 3, 3, 3, 5], [1, 1, 2, 2, 3, 3, 4, 4], [1, 1, 2, 2, 3, 3, 8], [1, 1, 2, 2, 3, 4, 7], [1, 1, 2, 2, 3, 5, 6], [1, 1, 2, 2, 3, 11], [1, 1, 2, 2, 4, 4, 6], [1, 1, 2, 2, 4, 5, 5], [1, 1, 2, 2, 4, 10], [1, 1, 2, 2, 5, 9], [1, 1, 2, 2, 6, 8], [1, 1, 2, 2, 7, 7], [1, 1, 2, 2, 14], [1, 1, 2, 3, 3, 3, 3, 4], [1, 1, 2, 3, 3, 3, 7], [1, 1, 2, 3, 3, 4, 6], [1, 1, 2, 3, 3, 5, 5], [1, 1, 2, 3, 3, 10], [1, 1, 2, 3, 4, 4, 5], [1, 1, 2, 3, 4, 9], [1, 1, 2, 3, 5, 8], [1, 1, 2, 3, 6, 7], [1, 1, 2, 3, 13], [1, 1, 2, 4, 4, 4, 4], [1, 1, 2, 4, 4, 8], [1, 1, 2, 4, 5, 7], [1, 1, 2, 4, 6, 6], [1, 1, 2, 4, 12], [1, 1, 2, 5, 5, 6], [1, 1, 2, 5, 11], [1, 1, 2, 6, 10], [1, 1, 2, 7, 9], [1, 1, 2, 8, 8], [1, 1, 2, 16], [1, 1, 3, 3, 3, 3, 3, 3], [1, 1, 3, 3, 3, 3, 6], [1, 1, 3, 3, 3, 4, 5], [1, 1, 3, 3, 3, 9], [1, 1, 3, 3, 4, 4, 4], [1, 1, 3, 3, 4, 8], [1, 1, 3, 3, 5, 7], [1, 1, 3, 3, 6, 6], [1, 1, 3, 3, 12], [1, 1, 3, 4, 4, 7], [1, 1, 3, 4, 5, 6], [1, 1, 3, 4, 11], [1, 1, 3, 5, 5, 5], [1, 1, 3, 5, 10], [1, 1, 3, 6, 9], [1, 1, 3, 7, 8], [1, 1, 3, 15], [1, 1, 4, 4, 4, 6], [1, 1, 4, 4, 5, 5], [1, 1, 4, 4, 10], [1, 1, 4, 5, 9], [1, 1, 4, 6, 8], [1, 1, 4, 7, 7], [1, 1, 4, 14], [1, 1, 5, 5, 8], [1, 1, 5, 6, 7], [1, 1, 5, 13], [1, 1, 6, 6, 6], [1, 1, 6, 12], [1, 1, 7, 11], [1, 1, 8, 10], [1, 1, 9, 9], [1, 1, 18], [1, 2, 2, 2, 2, 2, 2, 2, 2, 3], [1, 2, 2, 2, 2, 2, 2, 2, 5], [1, 2, 2, 2, 2, 2, 2, 3, 4], [1, 2, 2, 2, 2, 2, 2, 7], [1, 2, 2, 2, 2, 2, 3, 3, 3], [1, 2, 2, 2, 2, 2, 3, 6], [1, 2, 2, 2, 2, 2, 4, 5], [1, 2, 2, 2, 2, 2, 9], [1, 2, 2, 2, 2, 3, 3, 5], [1, 2, 2, 2, 2, 3, 4, 4], [1, 2, 2, 2, 2, 3, 8], [1, 2, 2, 2, 2, 4, 7], [1, 2, 2, 2, 2, 5, 6], [1, 2, 2, 2, 2, 11], [1, 2, 2, 2, 3, 3, 3, 4], [1, 2, 2, 2, 3, 3, 7], [1, 2, 2, 2, 3, 4, 6], [1, 2, 2, 2, 3, 5, 5], [1, 2, 2, 2, 3, 10], [1, 2, 2, 2, 4, 4, 5], [1, 2, 2, 2, 4, 9], [1, 2, 2, 2, 5, 8], [1, 2, 2, 2, 6, 7], [1, 2, 2, 2, 13], [1, 2, 2, 3, 3, 3, 3, 3], [1, 2, 2, 3, 3, 3, 6], [1, 2, 2, 3, 3, 4, 5], [1, 2, 2, 3, 3, 9], [1, 2, 2, 3, 4, 4, 4], [1, 2, 2, 3, 4, 8], [1, 2, 2, 3, 5, 7], [1, 2, 2, 3, 6, 6], [1, 2, 2, 3, 12], [1, 2, 2, 4, 4, 7], [1, 2, 2, 4, 5, 6], [1, 2, 2, 4, 11], [1, 2, 2, 5, 5, 5], [1, 2, 2, 5, 10], [1, 2, 2, 6, 9], [1, 2, 2, 7, 8], [1, 2, 2, 15], [1, 2, 3, 3, 3, 3, 5], [1, 2, 3, 3, 3, 4, 4], [1, 2, 3, 3, 3, 8], [1, 2, 3, 3, 4, 7], [1, 2, 3, 3, 5, 6], [1, 2, 3, 3, 11], [1, 2, 3, 4, 4, 6], [1, 2, 3, 4, 5, 5], [1, 2, 3, 4, 10], [1, 2, 3, 5, 9], [1, 2, 3, 6, 8], [1, 2, 3, 7, 7], [1, 2, 3, 14], [1, 2, 4, 4, 4, 5], [1, 2, 4, 4, 9], [1, 2, 4, 5, 8], [1, 2, 4, 6, 7], [1, 2, 4, 13], [1, 2, 5, 5, 7], [1, 2, 5, 6, 6], [1, 2, 5, 12], [1, 2, 6, 11], [1, 2, 7, 10], [1, 2, 8, 9], [1, 2, 17], [1, 3, 3, 3, 3, 3, 4], [1, 3, 3, 3, 3, 7], [1, 3, 3, 3, 4, 6], [1, 3, 3, 3, 5, 5], [1, 3, 3, 3, 10], [1, 3, 3, 4, 4, 5], [1, 3, 3, 4, 9], [1, 3, 3, 5, 8], [1, 3, 3, 6, 7], [1, 3, 3, 13], [1, 3, 4, 4, 4, 4], [1, 3, 4, 4, 8], [1, 3, 4, 5, 7], [1, 3, 4, 6, 6], [1, 3, 4, 12], [1, 3, 5, 5, 6], [1, 3, 5, 11], [1, 3, 6, 10], [1, 3, 7, 9], [1, 3, 8, 8], [1, 3, 16], [1, 4, 4, 4, 7], [1, 4, 4, 5, 6], [1, 4, 4, 11], [1, 4, 5, 5, 5], [1, 4, 5, 10], [1, 4, 6, 9], [1, 4, 7, 8], [1, 4, 15], [1, 5, 5, 9], [1, 5, 6, 8], [1, 5, 7, 7], [1, 5, 14], [1, 6, 6, 7], [1, 6, 13], [1, 7, 12], [1, 8, 11], [1, 9, 10], [1, 19], [2, 2, 2, 2, 2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 2, 2, 2, 2, 4], [2, 2, 2, 2, 2, 2, 2, 3, 3], [2, 2, 2, 2, 2, 2, 2, 6], [2, 2, 2, 2, 2, 2, 3, 5], [2, 2, 2, 2, 2, 2, 4, 4], [2, 2, 2, 2, 2, 2, 8], [2, 2, 2, 2, 2, 3, 3, 4], [2, 2, 2, 2, 2, 3, 7], [2, 2, 2, 2, 2, 4, 6], [2, 2, 2, 2, 2, 5, 5], [2, 2, 2, 2, 2, 10], [2, 2, 2, 2, 3, 3, 3, 3], [2, 2, 2, 2, 3, 3, 6], [2, 2, 2, 2, 3, 4, 5], [2, 2, 2, 2, 3, 9], [2, 2, 2, 2, 4, 4, 4], [2, 2, 2, 2, 4, 8], [2, 2, 2, 2, 5, 7], [2, 2, 2, 2, 6, 6], [2, 2, 2, 2, 12], [2, 2, 2, 3, 3, 3, 5], [2, 2, 2, 3, 3, 4, 4], [2, 2, 2, 3, 3, 8], [2, 2, 2, 3, 4, 7], [2, 2, 2, 3, 5, 6], [2, 2, 2, 3, 11], [2, 2, 2, 4, 4, 6], [2, 2, 2, 4, 5, 5], [2, 2, 2, 4, 10], [2, 2, 2, 5, 9], [2, 2, 2, 6, 8], [2, 2, 2, 7, 7], [2, 2, 2, 14], [2, 2, 3, 3, 3, 3, 4], [2, 2, 3, 3, 3, 7], [2, 2, 3, 3, 4, 6], [2, 2, 3, 3, 5, 5], [2, 2, 3, 3, 10], [2, 2, 3, 4, 4, 5], [2, 2, 3, 4, 9], [2, 2, 3, 5, 8], [2, 2, 3, 6, 7], [2, 2, 3, 13], [2, 2, 4, 4, 4, 4], [2, 2, 4, 4, 8], [2, 2, 4, 5, 7], [2, 2, 4, 6, 6], [2, 2, 4, 12], [2, 2, 5, 5, 6], [2, 2, 5, 11], [2, 2, 6, 10], [2, 2, 7, 9], [2, 2, 8, 8], [2, 2, 16], [2, 3, 3, 3, 3, 3, 3], [2, 3, 3, 3, 3, 6], [2, 3, 3, 3, 4, 5], [2, 3, 3, 3, 9], [2, 3, 3, 4, 4, 4], [2, 3, 3, 4, 8], [2, 3, 3, 5, 7], [2, 3, 3, 6, 6], [2, 3, 3, 12], [2, 3, 4, 4, 7], [2, 3, 4, 5, 6], [2, 3, 4, 11], [2, 3, 5, 5, 5], [2, 3, 5, 10], [2, 3, 6, 9], [2, 3, 7, 8], [2, 3, 15], [2, 4, 4, 4, 6], [2, 4, 4, 5, 5], [2, 4, 4, 10], [2, 4, 5, 9], [2, 4, 6, 8], [2, 4, 7, 7], [2, 4, 14], [2, 5, 5, 8], [2, 5, 6, 7], [2, 5, 13], [2, 6, 6, 6], [2, 6, 12], [2, 7, 11], [2, 8, 10], [2, 9, 9], [2, 18], [3, 3, 3, 3, 3, 5], [3, 3, 3, 3, 4, 4], [3, 3, 3, 3, 8], [3, 3, 3, 4, 7], [3, 3, 3, 5, 6], [3, 3, 3, 11], [3, 3, 4, 4, 6], [3, 3, 4, 5, 5], [3, 3, 4, 10], [3, 3, 5, 9], [3, 3, 6, 8], [3, 3, 7, 7], [3, 3, 14], [3, 4, 4, 4, 5], [3, 4, 4, 9], [3, 4, 5, 8], [3, 4, 6, 7], [3, 4, 13], [3, 5, 5, 7], [3, 5, 6, 6], [3, 5, 12], [3, 6, 11], [3, 7, 10], [3, 8, 9], [3, 17], [4, 4, 4, 4, 4], [4, 4, 4, 8], [4, 4, 5, 7], [4, 4, 6, 6], [4, 4, 12], [4, 5, 5, 6], [4, 5, 11], [4, 6, 10], [4, 7, 9], [4, 8, 8], [4, 16], [5, 5, 5, 5], [5, 5, 10], [5, 6, 9], [5, 7, 8], [5, 15], [6, 6, 8], [6, 7, 7], [6, 14], [7, 13], [8, 12], [9, 11], [10, 10], [20]]
	if n == 21:
		return [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 8], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 10], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 9], [1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 8], [1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 7], [1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1, 12], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 7], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4, 5], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 9], [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 5], [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 4], [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 8], [1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 7], [1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 11], [1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 7], [1, 1, 1, 1, 1, 1, 1, 1, 3, 4, 6], [1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 5], [1, 1, 1, 1, 1, 1, 1, 1, 3, 10], [1, 1, 1, 1, 1, 1, 1, 1, 4, 4, 5], [1, 1, 1, 1, 1, 1, 1, 1, 4, 9], [1, 1, 1, 1, 1, 1, 1, 1, 5, 8], [1, 1, 1, 1, 1, 1, 1, 1, 6, 7], [1, 1, 1, 1, 1, 1, 1, 1, 13], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 6], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 5], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 4, 4], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 8], [1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4], [1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 7], [1, 1, 1, 1, 1, 1, 1, 2, 2, 4, 6], [1, 1, 1, 1, 1, 1, 1, 2, 2, 5, 5], [1, 1, 1, 1, 1, 1, 1, 2, 2, 10], [1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 6], [1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5], [1, 1, 1, 1, 1, 1, 1, 2, 3, 9], [1, 1, 1, 1, 1, 1, 1, 2, 4, 4, 4], [1, 1, 1, 1, 1, 1, 1, 2, 4, 8], [1, 1, 1, 1, 1, 1, 1, 2, 5, 7], [1, 1, 1, 1, 1, 1, 1, 2, 6, 6], [1, 1, 1, 1, 1, 1, 1, 2, 12], [1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 5], [1, 1, 1, 1, 1, 1, 1, 3, 3, 4, 4], [1, 1, 1, 1, 1, 1, 1, 3, 3, 8], [1, 1, 1, 1, 1, 1, 1, 3, 4, 7], [1, 1, 1, 1, 1, 1, 1, 3, 5, 6], [1, 1, 1, 1, 1, 1, 1, 3, 11], [1, 1, 1, 1, 1, 1, 1, 4, 4, 6], [1, 1, 1, 1, 1, 1, 1, 4, 5, 5], [1, 1, 1, 1, 1, 1, 1, 4, 10], [1, 1, 1, 1, 1, 1, 1, 5, 9], [1, 1, 1, 1, 1, 1, 1, 6, 8], [1, 1, 1, 1, 1, 1, 1, 7, 7], [1, 1, 1, 1, 1, 1, 1, 14], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 5], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4], [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 7], [1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3], [1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 6], [1, 1, 1, 1, 1, 1, 2, 2, 2, 4, 5], [1, 1, 1, 1, 1, 1, 2, 2, 2, 9], [1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 5], [1, 1, 1, 1, 1, 1, 2, 2, 3, 4, 4], [1, 1, 1, 1, 1, 1, 2, 2, 3, 8], [1, 1, 1, 1, 1, 1, 2, 2, 4, 7], [1, 1, 1, 1, 1, 1, 2, 2, 5, 6], [1, 1, 1, 1, 1, 1, 2, 2, 11], [1, 1, 1, 1, 1, 1, 2, 3, 3, 3, 4], [1, 1, 1, 1, 1, 1, 2, 3, 3, 7], [1, 1, 1, 1, 1, 1, 2, 3, 4, 6], [1, 1, 1, 1, 1, 1, 2, 3, 5, 5], [1, 1, 1, 1, 1, 1, 2, 3, 10], [1, 1, 1, 1, 1, 1, 2, 4, 4, 5], [1, 1, 1, 1, 1, 1, 2, 4, 9], [1, 1, 1, 1, 1, 1, 2, 5, 8], [1, 1, 1, 1, 1, 1, 2, 6, 7], [1, 1, 1, 1, 1, 1, 2, 13], [1, 1, 1, 1, 1, 1, 3, 3, 3, 3, 3], [1, 1, 1, 1, 1, 1, 3, 3, 3, 6], [1, 1, 1, 1, 1, 1, 3, 3, 4, 5], [1, 1, 1, 1, 1, 1, 3, 3, 9], [1, 1, 1, 1, 1, 1, 3, 4, 4, 4], [1, 1, 1, 1, 1, 1, 3, 4, 8], [1, 1, 1, 1, 1, 1, 3, 5, 7], [1, 1, 1, 1, 1, 1, 3, 6, 6], [1, 1, 1, 1, 1, 1, 3, 12], [1, 1, 1, 1, 1, 1, 4, 4, 7], [1, 1, 1, 1, 1, 1, 4, 5, 6], [1, 1, 1, 1, 1, 1, 4, 11], [1, 1, 1, 1, 1, 1, 5, 5, 5], [1, 1, 1, 1, 1, 1, 5, 10], [1, 1, 1, 1, 1, 1, 6, 9], [1, 1, 1, 1, 1, 1, 7, 8], [1, 1, 1, 1, 1, 1, 15], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 4], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 6], [1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5], [1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 4], [1, 1, 1, 1, 1, 2, 2, 2, 2, 8], [1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4], [1, 1, 1, 1, 1, 2, 2, 2, 3, 7], [1, 1, 1, 1, 1, 2, 2, 2, 4, 6], [1, 1, 1, 1, 1, 2, 2, 2, 5, 5], [1, 1, 1, 1, 1, 2, 2, 2, 10], [1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3], [1, 1, 1, 1, 1, 2, 2, 3, 3, 6], [1, 1, 1, 1, 1, 2, 2, 3, 4, 5], [1, 1, 1, 1, 1, 2, 2, 3, 9], [1, 1, 1, 1, 1, 2, 2, 4, 4, 4], [1, 1, 1, 1, 1, 2, 2, 4, 8], [1, 1, 1, 1, 1, 2, 2, 5, 7], [1, 1, 1, 1, 1, 2, 2, 6, 6], [1, 1, 1, 1, 1, 2, 2, 12], [1, 1, 1, 1, 1, 2, 3, 3, 3, 5], [1, 1, 1, 1, 1, 2, 3, 3, 4, 4], [1, 1, 1, 1, 1, 2, 3, 3, 8], [1, 1, 1, 1, 1, 2, 3, 4, 7], [1, 1, 1, 1, 1, 2, 3, 5, 6], [1, 1, 1, 1, 1, 2, 3, 11], [1, 1, 1, 1, 1, 2, 4, 4, 6], [1, 1, 1, 1, 1, 2, 4, 5, 5], [1, 1, 1, 1, 1, 2, 4, 10], [1, 1, 1, 1, 1, 2, 5, 9], [1, 1, 1, 1, 1, 2, 6, 8], [1, 1, 1, 1, 1, 2, 7, 7], [1, 1, 1, 1, 1, 2, 14], [1, 1, 1, 1, 1, 3, 3, 3, 3, 4], [1, 1, 1, 1, 1, 3, 3, 3, 7], [1, 1, 1, 1, 1, 3, 3, 4, 6], [1, 1, 1, 1, 1, 3, 3, 5, 5], [1, 1, 1, 1, 1, 3, 3, 10], [1, 1, 1, 1, 1, 3, 4, 4, 5], [1, 1, 1, 1, 1, 3, 4, 9], [1, 1, 1, 1, 1, 3, 5, 8], [1, 1, 1, 1, 1, 3, 6, 7], [1, 1, 1, 1, 1, 3, 13], [1, 1, 1, 1, 1, 4, 4, 4, 4], [1, 1, 1, 1, 1, 4, 4, 8], [1, 1, 1, 1, 1, 4, 5, 7], [1, 1, 1, 1, 1, 4, 6, 6], [1, 1, 1, 1, 1, 4, 12], [1, 1, 1, 1, 1, 5, 5, 6], [1, 1, 1, 1, 1, 5, 11], [1, 1, 1, 1, 1, 6, 10], [1, 1, 1, 1, 1, 7, 9], [1, 1, 1, 1, 1, 8, 8], [1, 1, 1, 1, 1, 16], [1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3], [1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 5], [1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 4], [1, 1, 1, 1, 2, 2, 2, 2, 2, 7], [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3], [1, 1, 1, 1, 2, 2, 2, 2, 3, 6], [1, 1, 1, 1, 2, 2, 2, 2, 4, 5], [1, 1, 1, 1, 2, 2, 2, 2, 9], [1, 1, 1, 1, 2, 2, 2, 3, 3, 5], [1, 1, 1, 1, 2, 2, 2, 3, 4, 4], [1, 1, 1, 1, 2, 2, 2, 3, 8], [1, 1, 1, 1, 2, 2, 2, 4, 7], [1, 1, 1, 1, 2, 2, 2, 5, 6], [1, 1, 1, 1, 2, 2, 2, 11], [1, 1, 1, 1, 2, 2, 3, 3, 3, 4], [1, 1, 1, 1, 2, 2, 3, 3, 7], [1, 1, 1, 1, 2, 2, 3, 4, 6], [1, 1, 1, 1, 2, 2, 3, 5, 5], [1, 1, 1, 1, 2, 2, 3, 10], [1, 1, 1, 1, 2, 2, 4, 4, 5], [1, 1, 1, 1, 2, 2, 4, 9], [1, 1, 1, 1, 2, 2, 5, 8], [1, 1, 1, 1, 2, 2, 6, 7], [1, 1, 1, 1, 2, 2, 13], [1, 1, 1, 1, 2, 3, 3, 3, 3, 3], [1, 1, 1, 1, 2, 3, 3, 3, 6], [1, 1, 1, 1, 2, 3, 3, 4, 5], [1, 1, 1, 1, 2, 3, 3, 9], [1, 1, 1, 1, 2, 3, 4, 4, 4], [1, 1, 1, 1, 2, 3, 4, 8], [1, 1, 1, 1, 2, 3, 5, 7], [1, 1, 1, 1, 2, 3, 6, 6], [1, 1, 1, 1, 2, 3, 12], [1, 1, 1, 1, 2, 4, 4, 7], [1, 1, 1, 1, 2, 4, 5, 6], [1, 1, 1, 1, 2, 4, 11], [1, 1, 1, 1, 2, 5, 5, 5], [1, 1, 1, 1, 2, 5, 10], [1, 1, 1, 1, 2, 6, 9], [1, 1, 1, 1, 2, 7, 8], [1, 1, 1, 1, 2, 15], [1, 1, 1, 1, 3, 3, 3, 3, 5], [1, 1, 1, 1, 3, 3, 3, 4, 4], [1, 1, 1, 1, 3, 3, 3, 8], [1, 1, 1, 1, 3, 3, 4, 7], [1, 1, 1, 1, 3, 3, 5, 6], [1, 1, 1, 1, 3, 3, 11], [1, 1, 1, 1, 3, 4, 4, 6], [1, 1, 1, 1, 3, 4, 5, 5], [1, 1, 1, 1, 3, 4, 10], [1, 1, 1, 1, 3, 5, 9], [1, 1, 1, 1, 3, 6, 8], [1, 1, 1, 1, 3, 7, 7], [1, 1, 1, 1, 3, 14], [1, 1, 1, 1, 4, 4, 4, 5], [1, 1, 1, 1, 4, 4, 9], [1, 1, 1, 1, 4, 5, 8], [1, 1, 1, 1, 4, 6, 7], [1, 1, 1, 1, 4, 13], [1, 1, 1, 1, 5, 5, 7], [1, 1, 1, 1, 5, 6, 6], [1, 1, 1, 1, 5, 12], [1, 1, 1, 1, 6, 11], [1, 1, 1, 1, 7, 10], [1, 1, 1, 1, 8, 9], [1, 1, 1, 1, 17], [1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2], [1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 4], [1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3], [1, 1, 1, 2, 2, 2, 2, 2, 2, 6], [1, 1, 1, 2, 2, 2, 2, 2, 3, 5], [1, 1, 1, 2, 2, 2, 2, 2, 4, 4], [1, 1, 1, 2, 2, 2, 2, 2, 8], [1, 1, 1, 2, 2, 2, 2, 3, 3, 4], [1, 1, 1, 2, 2, 2, 2, 3, 7], [1, 1, 1, 2, 2, 2, 2, 4, 6], [1, 1, 1, 2, 2, 2, 2, 5, 5], [1, 1, 1, 2, 2, 2, 2, 10], [1, 1, 1, 2, 2, 2, 3, 3, 3, 3], [1, 1, 1, 2, 2, 2, 3, 3, 6], [1, 1, 1, 2, 2, 2, 3, 4, 5], [1, 1, 1, 2, 2, 2, 3, 9], [1, 1, 1, 2, 2, 2, 4, 4, 4], [1, 1, 1, 2, 2, 2, 4, 8], [1, 1, 1, 2, 2, 2, 5, 7], [1, 1, 1, 2, 2, 2, 6, 6], [1, 1, 1, 2, 2, 2, 12], [1, 1, 1, 2, 2, 3, 3, 3, 5], [1, 1, 1, 2, 2, 3, 3, 4, 4], [1, 1, 1, 2, 2, 3, 3, 8], [1, 1, 1, 2, 2, 3, 4, 7], [1, 1, 1, 2, 2, 3, 5, 6], [1, 1, 1, 2, 2, 3, 11], [1, 1, 1, 2, 2, 4, 4, 6], [1, 1, 1, 2, 2, 4, 5, 5], [1, 1, 1, 2, 2, 4, 10], [1, 1, 1, 2, 2, 5, 9], [1, 1, 1, 2, 2, 6, 8], [1, 1, 1, 2, 2, 7, 7], [1, 1, 1, 2, 2, 14], [1, 1, 1, 2, 3, 3, 3, 3, 4], [1, 1, 1, 2, 3, 3, 3, 7], [1, 1, 1, 2, 3, 3, 4, 6], [1, 1, 1, 2, 3, 3, 5, 5], [1, 1, 1, 2, 3, 3, 10], [1, 1, 1, 2, 3, 4, 4, 5], [1, 1, 1, 2, 3, 4, 9], [1, 1, 1, 2, 3, 5, 8], [1, 1, 1, 2, 3, 6, 7], [1, 1, 1, 2, 3, 13], [1, 1, 1, 2, 4, 4, 4, 4], [1, 1, 1, 2, 4, 4, 8], [1, 1, 1, 2, 4, 5, 7], [1, 1, 1, 2, 4, 6, 6], [1, 1, 1, 2, 4, 12], [1, 1, 1, 2, 5, 5, 6], [1, 1, 1, 2, 5, 11], [1, 1, 1, 2, 6, 10], [1, 1, 1, 2, 7, 9], [1, 1, 1, 2, 8, 8], [1, 1, 1, 2, 16], [1, 1, 1, 3, 3, 3, 3, 3, 3], [1, 1, 1, 3, 3, 3, 3, 6], [1, 1, 1, 3, 3, 3, 4, 5], [1, 1, 1, 3, 3, 3, 9], [1, 1, 1, 3, 3, 4, 4, 4], [1, 1, 1, 3, 3, 4, 8], [1, 1, 1, 3, 3, 5, 7], [1, 1, 1, 3, 3, 6, 6], [1, 1, 1, 3, 3, 12], [1, 1, 1, 3, 4, 4, 7], [1, 1, 1, 3, 4, 5, 6], [1, 1, 1, 3, 4, 11], [1, 1, 1, 3, 5, 5, 5], [1, 1, 1, 3, 5, 10], [1, 1, 1, 3, 6, 9], [1, 1, 1, 3, 7, 8], [1, 1, 1, 3, 15], [1, 1, 1, 4, 4, 4, 6], [1, 1, 1, 4, 4, 5, 5], [1, 1, 1, 4, 4, 10], [1, 1, 1, 4, 5, 9], [1, 1, 1, 4, 6, 8], [1, 1, 1, 4, 7, 7], [1, 1, 1, 4, 14], [1, 1, 1, 5, 5, 8], [1, 1, 1, 5, 6, 7], [1, 1, 1, 5, 13], [1, 1, 1, 6, 6, 6], [1, 1, 1, 6, 12], [1, 1, 1, 7, 11], [1, 1, 1, 8, 10], [1, 1, 1, 9, 9], [1, 1, 1, 18], [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3], [1, 1, 2, 2, 2, 2, 2, 2, 2, 5], [1, 1, 2, 2, 2, 2, 2, 2, 3, 4], [1, 1, 2, 2, 2, 2, 2, 2, 7], [1, 1, 2, 2, 2, 2, 2, 3, 3, 3], [1, 1, 2, 2, 2, 2, 2, 3, 6], [1, 1, 2, 2, 2, 2, 2, 4, 5], [1, 1, 2, 2, 2, 2, 2, 9], [1, 1, 2, 2, 2, 2, 3, 3, 5], [1, 1, 2, 2, 2, 2, 3, 4, 4], [1, 1, 2, 2, 2, 2, 3, 8], [1, 1, 2, 2, 2, 2, 4, 7], [1, 1, 2, 2, 2, 2, 5, 6], [1, 1, 2, 2, 2, 2, 11], [1, 1, 2, 2, 2, 3, 3, 3, 4], [1, 1, 2, 2, 2, 3, 3, 7], [1, 1, 2, 2, 2, 3, 4, 6], [1, 1, 2, 2, 2, 3, 5, 5], [1, 1, 2, 2, 2, 3, 10], [1, 1, 2, 2, 2, 4, 4, 5], [1, 1, 2, 2, 2, 4, 9], [1, 1, 2, 2, 2, 5, 8], [1, 1, 2, 2, 2, 6, 7], [1, 1, 2, 2, 2, 13], [1, 1, 2, 2, 3, 3, 3, 3, 3], [1, 1, 2, 2, 3, 3, 3, 6], [1, 1, 2, 2, 3, 3, 4, 5], [1, 1, 2, 2, 3, 3, 9], [1, 1, 2, 2, 3, 4, 4, 4], [1, 1, 2, 2, 3, 4, 8], [1, 1, 2, 2, 3, 5, 7], [1, 1, 2, 2, 3, 6, 6], [1, 1, 2, 2, 3, 12], [1, 1, 2, 2, 4, 4, 7], [1, 1, 2, 2, 4, 5, 6], [1, 1, 2, 2, 4, 11], [1, 1, 2, 2, 5, 5, 5], [1, 1, 2, 2, 5, 10], [1, 1, 2, 2, 6, 9], [1, 1, 2, 2, 7, 8], [1, 1, 2, 2, 15], [1, 1, 2, 3, 3, 3, 3, 5], [1, 1, 2, 3, 3, 3, 4, 4], [1, 1, 2, 3, 3, 3, 8], [1, 1, 2, 3, 3, 4, 7], [1, 1, 2, 3, 3, 5, 6], [1, 1, 2, 3, 3, 11], [1, 1, 2, 3, 4, 4, 6], [1, 1, 2, 3, 4, 5, 5], [1, 1, 2, 3, 4, 10], [1, 1, 2, 3, 5, 9], [1, 1, 2, 3, 6, 8], [1, 1, 2, 3, 7, 7], [1, 1, 2, 3, 14], [1, 1, 2, 4, 4, 4, 5], [1, 1, 2, 4, 4, 9], [1, 1, 2, 4, 5, 8], [1, 1, 2, 4, 6, 7], [1, 1, 2, 4, 13], [1, 1, 2, 5, 5, 7], [1, 1, 2, 5, 6, 6], [1, 1, 2, 5, 12], [1, 1, 2, 6, 11], [1, 1, 2, 7, 10], [1, 1, 2, 8, 9], [1, 1, 2, 17], [1, 1, 3, 3, 3, 3, 3, 4], [1, 1, 3, 3, 3, 3, 7], [1, 1, 3, 3, 3, 4, 6], [1, 1, 3, 3, 3, 5, 5], [1, 1, 3, 3, 3, 10], [1, 1, 3, 3, 4, 4, 5], [1, 1, 3, 3, 4, 9], [1, 1, 3, 3, 5, 8], [1, 1, 3, 3, 6, 7], [1, 1, 3, 3, 13], [1, 1, 3, 4, 4, 4, 4], [1, 1, 3, 4, 4, 8], [1, 1, 3, 4, 5, 7], [1, 1, 3, 4, 6, 6], [1, 1, 3, 4, 12], [1, 1, 3, 5, 5, 6], [1, 1, 3, 5, 11], [1, 1, 3, 6, 10], [1, 1, 3, 7, 9], [1, 1, 3, 8, 8], [1, 1, 3, 16], [1, 1, 4, 4, 4, 7], [1, 1, 4, 4, 5, 6], [1, 1, 4, 4, 11], [1, 1, 4, 5, 5, 5], [1, 1, 4, 5, 10], [1, 1, 4, 6, 9], [1, 1, 4, 7, 8], [1, 1, 4, 15], [1, 1, 5, 5, 9], [1, 1, 5, 6, 8], [1, 1, 5, 7, 7], [1, 1, 5, 14], [1, 1, 6, 6, 7], [1, 1, 6, 13], [1, 1, 7, 12], [1, 1, 8, 11], [1, 1, 9, 10], [1, 1, 19], [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], [1, 2, 2, 2, 2, 2, 2, 2, 2, 4], [1, 2, 2, 2, 2, 2, 2, 2, 3, 3], [1, 2, 2, 2, 2, 2, 2, 2, 6], [1, 2, 2, 2, 2, 2, 2, 3, 5], [1, 2, 2, 2, 2, 2, 2, 4, 4], [1, 2, 2, 2, 2, 2, 2, 8], [1, 2, 2, 2, 2, 2, 3, 3, 4], [1, 2, 2, 2, 2, 2, 3, 7], [1, 2, 2, 2, 2, 2, 4, 6], [1, 2, 2, 2, 2, 2, 5, 5], [1, 2, 2, 2, 2, 2, 10], [1, 2, 2, 2, 2, 3, 3, 3, 3], [1, 2, 2, 2, 2, 3, 3, 6], [1, 2, 2, 2, 2, 3, 4, 5], [1, 2, 2, 2, 2, 3, 9], [1, 2, 2, 2, 2, 4, 4, 4], [1, 2, 2, 2, 2, 4, 8], [1, 2, 2, 2, 2, 5, 7], [1, 2, 2, 2, 2, 6, 6], [1, 2, 2, 2, 2, 12], [1, 2, 2, 2, 3, 3, 3, 5], [1, 2, 2, 2, 3, 3, 4, 4], [1, 2, 2, 2, 3, 3, 8], [1, 2, 2, 2, 3, 4, 7], [1, 2, 2, 2, 3, 5, 6], [1, 2, 2, 2, 3, 11], [1, 2, 2, 2, 4, 4, 6], [1, 2, 2, 2, 4, 5, 5], [1, 2, 2, 2, 4, 10], [1, 2, 2, 2, 5, 9], [1, 2, 2, 2, 6, 8], [1, 2, 2, 2, 7, 7], [1, 2, 2, 2, 14], [1, 2, 2, 3, 3, 3, 3, 4], [1, 2, 2, 3, 3, 3, 7], [1, 2, 2, 3, 3, 4, 6], [1, 2, 2, 3, 3, 5, 5], [1, 2, 2, 3, 3, 10], [1, 2, 2, 3, 4, 4, 5], [1, 2, 2, 3, 4, 9], [1, 2, 2, 3, 5, 8], [1, 2, 2, 3, 6, 7], [1, 2, 2, 3, 13], [1, 2, 2, 4, 4, 4, 4], [1, 2, 2, 4, 4, 8], [1, 2, 2, 4, 5, 7], [1, 2, 2, 4, 6, 6], [1, 2, 2, 4, 12], [1, 2, 2, 5, 5, 6], [1, 2, 2, 5, 11], [1, 2, 2, 6, 10], [1, 2, 2, 7, 9], [1, 2, 2, 8, 8], [1, 2, 2, 16], [1, 2, 3, 3, 3, 3, 3, 3], [1, 2, 3, 3, 3, 3, 6], [1, 2, 3, 3, 3, 4, 5], [1, 2, 3, 3, 3, 9], [1, 2, 3, 3, 4, 4, 4], [1, 2, 3, 3, 4, 8], [1, 2, 3, 3, 5, 7], [1, 2, 3, 3, 6, 6], [1, 2, 3, 3, 12], [1, 2, 3, 4, 4, 7], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 11], [1, 2, 3, 5, 5, 5], [1, 2, 3, 5, 10], [1, 2, 3, 6, 9], [1, 2, 3, 7, 8], [1, 2, 3, 15], [1, 2, 4, 4, 4, 6], [1, 2, 4, 4, 5, 5], [1, 2, 4, 4, 10], [1, 2, 4, 5, 9], [1, 2, 4, 6, 8], [1, 2, 4, 7, 7], [1, 2, 4, 14], [1, 2, 5, 5, 8], [1, 2, 5, 6, 7], [1, 2, 5, 13], [1, 2, 6, 6, 6], [1, 2, 6, 12], [1, 2, 7, 11], [1, 2, 8, 10], [1, 2, 9, 9], [1, 2, 18], [1, 3, 3, 3, 3, 3, 5], [1, 3, 3, 3, 3, 4, 4], [1, 3, 3, 3, 3, 8], [1, 3, 3, 3, 4, 7], [1, 3, 3, 3, 5, 6], [1, 3, 3, 3, 11], [1, 3, 3, 4, 4, 6], [1, 3, 3, 4, 5, 5], [1, 3, 3, 4, 10], [1, 3, 3, 5, 9], [1, 3, 3, 6, 8], [1, 3, 3, 7, 7], [1, 3, 3, 14], [1, 3, 4, 4, 4, 5], [1, 3, 4, 4, 9], [1, 3, 4, 5, 8], [1, 3, 4, 6, 7], [1, 3, 4, 13], [1, 3, 5, 5, 7], [1, 3, 5, 6, 6], [1, 3, 5, 12], [1, 3, 6, 11], [1, 3, 7, 10], [1, 3, 8, 9], [1, 3, 17], [1, 4, 4, 4, 4, 4], [1, 4, 4, 4, 8], [1, 4, 4, 5, 7], [1, 4, 4, 6, 6], [1, 4, 4, 12], [1, 4, 5, 5, 6], [1, 4, 5, 11], [1, 4, 6, 10], [1, 4, 7, 9], [1, 4, 8, 8], [1, 4, 16], [1, 5, 5, 5, 5], [1, 5, 5, 10], [1, 5, 6, 9], [1, 5, 7, 8], [1, 5, 15], [1, 6, 6, 8], [1, 6, 7, 7], [1, 6, 14], [1, 7, 13], [1, 8, 12], [1, 9, 11], [1, 10, 10], [1, 20], [2, 2, 2, 2, 2, 2, 2, 2, 2, 3], [2, 2, 2, 2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 2, 2, 2, 3, 4], [2, 2, 2, 2, 2, 2, 2, 7], [2, 2, 2, 2, 2, 2, 3, 3, 3], [2, 2, 2, 2, 2, 2, 3, 6], [2, 2, 2, 2, 2, 2, 4, 5], [2, 2, 2, 2, 2, 2, 9], [2, 2, 2, 2, 2, 3, 3, 5], [2, 2, 2, 2, 2, 3, 4, 4], [2, 2, 2, 2, 2, 3, 8], [2, 2, 2, 2, 2, 4, 7], [2, 2, 2, 2, 2, 5, 6], [2, 2, 2, 2, 2, 11], [2, 2, 2, 2, 3, 3, 3, 4], [2, 2, 2, 2, 3, 3, 7], [2, 2, 2, 2, 3, 4, 6], [2, 2, 2, 2, 3, 5, 5], [2, 2, 2, 2, 3, 10], [2, 2, 2, 2, 4, 4, 5], [2, 2, 2, 2, 4, 9], [2, 2, 2, 2, 5, 8], [2, 2, 2, 2, 6, 7], [2, 2, 2, 2, 13], [2, 2, 2, 3, 3, 3, 3, 3], [2, 2, 2, 3, 3, 3, 6], [2, 2, 2, 3, 3, 4, 5], [2, 2, 2, 3, 3, 9], [2, 2, 2, 3, 4, 4, 4], [2, 2, 2, 3, 4, 8], [2, 2, 2, 3, 5, 7], [2, 2, 2, 3, 6, 6], [2, 2, 2, 3, 12], [2, 2, 2, 4, 4, 7], [2, 2, 2, 4, 5, 6], [2, 2, 2, 4, 11], [2, 2, 2, 5, 5, 5], [2, 2, 2, 5, 10], [2, 2, 2, 6, 9], [2, 2, 2, 7, 8], [2, 2, 2, 15], [2, 2, 3, 3, 3, 3, 5], [2, 2, 3, 3, 3, 4, 4], [2, 2, 3, 3, 3, 8], [2, 2, 3, 3, 4, 7], [2, 2, 3, 3, 5, 6], [2, 2, 3, 3, 11], [2, 2, 3, 4, 4, 6], [2, 2, 3, 4, 5, 5], [2, 2, 3, 4, 10], [2, 2, 3, 5, 9], [2, 2, 3, 6, 8], [2, 2, 3, 7, 7], [2, 2, 3, 14], [2, 2, 4, 4, 4, 5], [2, 2, 4, 4, 9], [2, 2, 4, 5, 8], [2, 2, 4, 6, 7], [2, 2, 4, 13], [2, 2, 5, 5, 7], [2, 2, 5, 6, 6], [2, 2, 5, 12], [2, 2, 6, 11], [2, 2, 7, 10], [2, 2, 8, 9], [2, 2, 17], [2, 3, 3, 3, 3, 3, 4], [2, 3, 3, 3, 3, 7], [2, 3, 3, 3, 4, 6], [2, 3, 3, 3, 5, 5], [2, 3, 3, 3, 10], [2, 3, 3, 4, 4, 5], [2, 3, 3, 4, 9], [2, 3, 3, 5, 8], [2, 3, 3, 6, 7], [2, 3, 3, 13], [2, 3, 4, 4, 4, 4], [2, 3, 4, 4, 8], [2, 3, 4, 5, 7], [2, 3, 4, 6, 6], [2, 3, 4, 12], [2, 3, 5, 5, 6], [2, 3, 5, 11], [2, 3, 6, 10], [2, 3, 7, 9], [2, 3, 8, 8], [2, 3, 16], [2, 4, 4, 4, 7], [2, 4, 4, 5, 6], [2, 4, 4, 11], [2, 4, 5, 5, 5], [2, 4, 5, 10], [2, 4, 6, 9], [2, 4, 7, 8], [2, 4, 15], [2, 5, 5, 9], [2, 5, 6, 8], [2, 5, 7, 7], [2, 5, 14], [2, 6, 6, 7], [2, 6, 13], [2, 7, 12], [2, 8, 11], [2, 9, 10], [2, 19], [3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 6], [3, 3, 3, 3, 4, 5], [3, 3, 3, 3, 9], [3, 3, 3, 4, 4, 4], [3, 3, 3, 4, 8], [3, 3, 3, 5, 7], [3, 3, 3, 6, 6], [3, 3, 3, 12], [3, 3, 4, 4, 7], [3, 3, 4, 5, 6], [3, 3, 4, 11], [3, 3, 5, 5, 5], [3, 3, 5, 10], [3, 3, 6, 9], [3, 3, 7, 8], [3, 3, 15], [3, 4, 4, 4, 6], [3, 4, 4, 5, 5], [3, 4, 4, 10], [3, 4, 5, 9], [3, 4, 6, 8], [3, 4, 7, 7], [3, 4, 14], [3, 5, 5, 8], [3, 5, 6, 7], [3, 5, 13], [3, 6, 6, 6], [3, 6, 12], [3, 7, 11], [3, 8, 10], [3, 9, 9], [3, 18], [4, 4, 4, 4, 5], [4, 4, 4, 9], [4, 4, 5, 8], [4, 4, 6, 7], [4, 4, 13], [4, 5, 5, 7], [4, 5, 6, 6], [4, 5, 12], [4, 6, 11], [4, 7, 10], [4, 8, 9], [4, 17], [5, 5, 5, 6], [5, 5, 11], [5, 6, 10], [5, 7, 9], [5, 8, 8], [5, 16], [6, 6, 9], [6, 7, 8], [6, 15], [7, 7, 7], [7, 14], [8, 13], [9, 12], [10, 11], [21]]


import itertools

def combos(n):
	return [[1]] if n == 1 else list((i for (i, _) in itertools.groupby(sorted([[n]] + [sorted(j + [i]) for i in range(1, n) for j in combos(n - i)]))))


def combos(n):
	return list(part(n))

def part(n, k=1):
	yield [n]
	for i in range(k, n // 2 + 1):
		for p in part(n - i, i):
			yield ([i] + p)


def combos(n):
	mom_a = [[1]]
	i = 2
	while i <= n:
		tmp_a = [[i]]
		for lst in mom_a:
			tmp_a.insert(0, [1] + lst)
		for lst in mom_a:
			for j in range(len(lst)):
				tmp_lst = sorted(lst[:j] + [lst[j] + 1] + lst[j + 1:])
				if not tmp_lst in tmp_a:
					tmp_a.append(tmp_lst)
		mom_a = tmp_a
		i += 1
	return mom_a


def combos(n):
	(combinatorialations, answer, seen) = (map(lambda x: [x], list(range(1, n + 1))), [], set())
	while len(combinatorialations):
		acombo = combinatorialations.pop()
		thesum = sum(acombo)
		if thesum == n:
			answer.append(acombo)
			continue
		for i in range(1, n):
			if i + thesum > n:
				break
			newcombo = sorted(acombo + [i])
			tup = tuple(newcombo)
			if tup in seen:
				continue
			seen.add(tup)
			combinatorialations.append(newcombo)
	return answer


def combos(n):
	return combos_between(1, n)

def combos_between(m, n):
	if n == 1:
		return [[1]]
	result = [[n]]
	for x in range(m, n // 2 + 1):
		for combo in combos_between(x, n - x):
			result.append([x] + combo)
	return result