Some time ago Leonid have known about idempotent functions. Idempotent function defined on a set {1, 2, ..., n} is such function <image>, that for any <image> the formula g(g(x)) = g(x) holds.

Let's denote as f(k)(x) the function f applied k times to the value x. More formally, f(1)(x) = f(x), f(k)(x) = f(f(k - 1)(x)) for each k > 1.

You are given some function <image>. Your task is to find minimum positive integer k such that function f(k)(x) is idempotent.

Input

In the first line of the input there is a single integer n (1 ≤ n ≤ 200) — the size of function f domain.

In the second line follow f(1), f(2), ..., f(n) (1 ≤ f(i) ≤ n for each 1 ≤ i ≤ n), the values of a function.

Output

Output minimum k such that function f(k)(x) is idempotent.

Examples

Input

4
1 2 2 4


Output

1


Input

3
2 3 3


Output

2


Input

3
2 3 1


Output

3

Note

In the first sample test function f(x) = f(1)(x) is already idempotent since f(f(1)) = f(1) = 1, f(f(2)) = f(2) = 2, f(f(3)) = f(3) = 2, f(f(4)) = f(4) = 4.

In the second sample test: 

  * function f(x) = f(1)(x) isn't idempotent because f(f(1)) = 3 but f(1) = 2; 
  * function f(x) = f(2)(x) is idempotent since for any x it is true that f(2)(x) = 3, so it is also true that f(2)(f(2)(x)) = 3. 



In the third sample test: 

  * function f(x) = f(1)(x) isn't idempotent because f(f(1)) = 3 but f(1) = 2; 
  * function f(f(x)) = f(2)(x) isn't idempotent because f(2)(f(2)(1)) = 2 but f(2)(1) = 3; 
  * function f(f(f(x))) = f(3)(x) is idempotent since it is identity function: f(3)(x) = x for any <image> meaning that the formula f(3)(f(3)(x)) = f(3)(x) also holds. 
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.util.ArrayDeque;
import java.io.InputStream;
import java.util.Random;
import java.util.Collection;
import java.math.BigInteger;
import java.io.PrintStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Queue;
import java.io.IOException;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author karan173
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskC
{
    int n;
    ArrayList<Integer> G[], revG[];
    long ans;
    SCC scc;
    int sizeComp[];
    int next[];

    public void solve(int testNumber, FastReader in, PrintWriter out)
    {
        n = in.ni ();
        next = new int[n];
        G = new ArrayList[n];
        revG = new ArrayList[n];
        for (int i = 0; i < n; i++)
        {
            G[i] = new ArrayList<Integer> ();
            revG[i] = new ArrayList<Integer> ();
        }
        for (int i = 0; i < n; i++)
        {
            int x = in.ni () - 1;
            next[i] = x;
            G[i].add (x);
            revG[x].add (i);
        }
        scc = new SCC ();
        scc.getSCC (G, revG);
        ans = 0;
        sizeComp = new int[scc.numComp];
        int compressed[] = new int[scc.numComp];
        Arrays.fill (compressed, -1);
        for (int i = 0; i < n; i++)
        {
            int x = scc.comp[i];
            int y = scc.comp[next[i]];
            //edge from x to y in compressed graph
            if (x != y)
            {
                compressed[x] = y;
            }
            sizeComp[x]++;
        }
        ans = sizeComp[0];
        for (int i = 0; i < scc.numComp; i++)
        {
            ans = lcm (ans, sizeComp[i]);
        }
        //back bfs
        int minDist[] = new int[scc.numComp];
        int size[] = new int[scc.numComp];
        Arrays.fill (minDist, -1);
        Queue<Integer> queue = new ArrayDeque<Integer> ();
        for (int i = 0; i < scc.numComp; i++)
        {
            if (compressed[i] == -1)
            {
                minDist[i] = 0;
                size[i] = sizeComp[i];
                queue.add (i);
            }
        }
        long base = ans;
        while (!queue.isEmpty ())
        {
            int x = queue.poll ();
            
                while (minDist[x] > ans)
                {
                    ans += base;
                }
            for (int i = 0; i < scc.numComp; i++)
            {
                if (compressed[i] == x)
                {
                    queue.add (i);
                    minDist[i] = minDist[x] + 1;
                    size[i] = size[x];
                }
            }
        }
        out.println (ans);

//        int n = in.ni ();
//        int next[] = new int[n];
//        int cur[] = new int[n];
//        for (int i = 0; i < n; i++)
//        {
//            cur[i] = next[i] = in.ni () - 1;
//        }
//        int k = 1;
//        int temp[] = new int[n];
//        while (!idempotent (cur))
//        {
////            if (k == 8)
////            {
////                for (int i = 0; i < n; i++)
////                {
////                    out.println ((i + 1) + "->" + (cur[i] + 1));
////                }
////            }
//            k++;
//            for (int i = 0; i < n; i++)
//            {
//                temp[i] = next[cur[i]];
//            }
//            int t[] = temp;
//            temp = cur;
//            cur = t;
//        }
//        out.println (k);
    }

    private long lcm(long x, long y)
    {
        return (x / MathUtils.gcd (x, y)) * y;
    }

    //    private boolean idempotent(int[] cur)
//    {
//        for (int i = 0; i < cur.length; i++)
//        {
//            if (cur[cur[i]] != cur[i])
//            {
//                return false;
//            }
//        }
//        return true;
//    }


}

class SCC
{
    public int numComp; //number of SCC
    public int comp[];  //component number of vertex i from [0, numComp)
    int n;
    ArrayList<Integer> revG[];
    /*
    takes as input graph and its reverse
    Kosaraju two pass algorithm
    for explanation see techniques
    Also note that we have proceeded in topological order of actual Graph while calculation comp[]
     */
    public void getSCC(ArrayList<Integer> G[], ArrayList<Integer> revG[])
    {
        this.revG = revG;
        numComp = 0;
        n = G.length;
        comp = new int[n];
        Arrays.fill (comp, -1);
        int revPostOrder[] = new TopoSort ().topoSort (G); //actually not topo order, coz graph is cyclic
        for (int x : revPostOrder)
        {
            if (comp[x] == -1)
            {
                dfs (x);
                numComp++;
            }
        }
    }

    private void dfs(int i)
    {
        comp[i] = numComp;
        for (int v : revG[i])
        {
            if (comp[v] != -1)
            {
                continue;
            }
            dfs (v);
        }
    }
}

class FastReader
{

    public InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public FastReader(InputStream stream)
    {
        this.stream = stream;
    }

    public int read()
    {
        if (numChars == -1)
        {
            throw new InputMismatchException ();
        }
        if (curChar >= numChars)
        {
            curChar = 0;
            try
            {
                numChars = stream.read (buf);
            } catch (IOException e)
            {
                throw new InputMismatchException ();
            }
            if (numChars <= 0)
            {
                return -1;
            }
        }
        return buf[curChar++];
    }

    public int ni()
    {
        int c = read ();
        while (isSpaceChar (c))
            c = read ();
        int sgn = 1;
        if (c == '-')
        {
            sgn = -1;
            c = read ();
        }
        int res = 0;
        do
        {
            if (c < '0' || c > '9')
            {
                throw new InputMismatchException ();
            }
            res *= 10;
            res += c - '0';
            c = read ();
        } while (!isSpaceChar (c));
        return res * sgn;
    }

    public boolean isSpaceChar(int c)
    {
        if (filter != null)
        {
            return filter.isSpaceChar (c);
        }
        return isWhitespace (c);
    }

    public static boolean isWhitespace(int c)
    {
        return c==' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
}

class MathUtils
{
    public static long gcd(long big, long small) // O(log min(a, b))
    {
        if (small == 0)
            return big;
        return gcd(small, big % small); // big%small<=small
    }


    // NCR DP
    // O(n*n) precomputation -> dp, no overflow
    
    
    /*factor sieve -> O(n/2) memory      */

    //    public static long fastMult( long a, long b, long m )
//    {
//        //from http://apps.topcoder.com/forums/?module=RevisionHistory&messageID=1221302
//        if(a>m)
//            a=a%m;
//        if(b>m)
//            b=b%m;
//        long ret = 0;
//        if(a<b)
//        {
//            long t = a;
//            a = b;
//            b = t;
//        }
//        while(b>0)
//        {
//            while(a<m)
//            {
//                if((b&1) != 0)
//                    ret += a;
//                a<<=1;
//                b>>=1;
//            }
//            a-=m;
//            while(ret>=m)
//                ret-=m;
//            if(a<b)
//            {
//                long t = a;
//                a = b;
//                b = t;
//            }
//        }
//        return ret;
//    }

}

class TopoSort
{
    boolean done[];
    int n;
    ArrayList<Integer> adjList[];
    public int topoOrder[];
    int revCtr;
    /*
    returns reversed post order of graph
    graph should be dag for order to be topologically sorted
     */
    public int[] topoSort(ArrayList<Integer> adjList[])
    {
        this.adjList = adjList;
        n = adjList.length;
        done = new boolean[n];
        topoOrder = new int[n];
        revCtr = n-1;
        for (int i = 0; i < n; i++)
        {
            if (!done[i])
            {
                done[i] = true;
                dfs (i);
            }
        }
        return topoOrder;
    }

    private void dfs(int i)
    {
        for (int v : adjList[i])
        {
            if(!done[v])
            {
                done[v] = true;
                dfs (v);
            }
        }
        topoOrder[revCtr--] = i;
    }
}
