Factors Up To N

You are given the following function, which returns the set of all factors of a positive integer n:

def factors(n):
    fact = set()
    for f in range(1, n + 1):
        if n % f == 0:
            fact.add(f)
    return fact

Write a function named factors_upto that accepts a positive integer n as argument. It should return a dictionary D whose keys are integers and whose values are sets. Each integer in the range from 1 to n, both endpoints included, is a key of D. The value corresponding to a key is the set of all factors of that key. This function must make use of factors.

Include the definition of factors in your answer as well, so that your code runs on its own.

You do not have to accept input from the user or print anything.

Example

factors_upto(4)  ->  {1: {1}, 2: {1, 2}, 3: {1, 3}, 4: {1, 2, 4}}

Your task

Implement this function:

def factors(n):

Write the function only — the arguments are read for you and the return value is printed automatically.

Arguments arrive as one Python literal per line, in this order: n.

Example

Input

4

Output

{1: {1}, 2: {1, 2}, 3: {1, 3}, 4: {1, 2, 4}}