#!/usr/bin/env python3

import itertools
import sys

def get_square_checker(max_):
    squares = set(itertools.takewhile(lambda x: x <= 2 * max_ - 1, (i ** 2 for i in itertools.count())))
    return lambda x: x in squares

def get_nexts(range_):
    pairs = filter(lambda pair: is_square(sum(pair)), itertools.combinations(range_, 2))
    nexts = {}
    for (a, b) in pairs:
        nexts.setdefault(a, set()).add(b)
        nexts.setdefault(b, set()).add(a)
    return nexts

def try_make_lists(current_list, used_digits, remaining_digits, nexts):
    # used_digits and remaining_digits are passed for performance reasons only.
    if not remaining_digits:
        yield current_list
    else:
        cur_digit = current_list[-1]
        for next_digit in nexts[cur_digit] - used_digits:
            yield from try_make_lists(current_list + [next_digit], used_digits | {next_digit}, remaining_digits - {next_digit}, nexts)

if __name__ == '__main__':
    max_ = int(sys.argv[1])
    range_ = range(1, max_ + 1)
    is_square = get_square_checker(max_=max_)
    nexts = get_nexts(range_=range_)

    for first_digit in range_:
        for r in try_make_lists([first_digit], {first_digit}, set(range_) - {first_digit}, nexts):
            print(r)