Under construction

Still being built. Things may change

Smallest Regular Subpolygon

Time limit2sMemory limit512 MB

Summary
Given a regular N-gon, find the smallest number of its vertices that themselves form a regular polygon.
Level

Medium6 of 10

Topics
Number theory, Math, Geometry, Combinatorics
Solved
No attempts yet

Problem

A regular NN-gon is given. Choose the smallest number of its vertices that also form a regular polygon.

Input

The input contains a single integer NN (3≤N≤10123 \le N \le 10^{12}).

Output

Print a single number: the smallest number of vertices of the given polygon that form a regular polygon.

Examples2

  1. Example 1

    Input
    5
    Expected output
    5

  2. Example 2

    Input
    21
    Expected output
    3