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.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		InputReader sc = new InputReader(new BufferedInputStream(System.in));
		PrintWriter out = new PrintWriter(new BufferedWriter(
				new OutputStreamWriter(System.out)));

		int size = sc.nextInt();
		ArrayList<Integer> stringGraph = new ArrayList<Integer>();
		for (int i = 0; i < size; i++) {
			stringGraph.add(sc.nextInt());
		}
		Graph g = new Graph(size, stringGraph);
		out.print(g.findIdempotent());

		out.flush();
		out.close();

	}

	public static long gcd(long a, long b) //valid for positive integers.
	{
		while(b > 0)
		{
			long c = a % b;
			a = b;
			b = c;
		}
		return a;
	}
	
	public static long lcm(long m, long n) {
		return (m*n)/gcd(m,n);
	}

}

class InputReader {
	BufferedReader reader;
	StringTokenizer tokenizer;

	public InputReader(InputStream stream) {
		reader = new BufferedReader(new InputStreamReader(stream));
		tokenizer = null;
	}

	public String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}
}

class GraphNode {

	private boolean visited;
	private int content;
	private ArrayList<Edge> edges;

	public int getContent() {
		return content;
	}

	public ArrayList<Edge> getInComes() {
		return (ArrayList<Edge>) edges.subList(1, edges.size() - 1);
	}

	public void addEdgeToInComes(Edge add) {
		this.edges.add(add);
	}

	public Edge getOutGoing() {
		return edges.get(0);
	}

	public void addOutGoingEdge(Edge add) {
		this.edges.add(0, add);
	}

	public GraphNode(int content) {
		this.content = content;
		this.edges = new ArrayList<Edge>();
		this.visited = false;
	}

	public int getInDegree() {
		return edges.subList(1, edges.size()).size();
	}

	public boolean isVisited() {
		return visited;
	}

	public void setVisited(boolean visited) {
		this.visited = visited;
	}

	public ArrayList<Edge> getEdges() {
		return this.edges;
	}
}

class Graph {
	private ArrayList<GraphNode> nodes;

	public Graph(int size, ArrayList<Integer> edges) {
		nodes = new ArrayList<GraphNode>();
		for (int i = 1; i <= size; i++) {
			nodes.add(new GraphNode(i));
		}
		for (int i = 0; i < edges.size(); i++) {
			addEdge(i + 1, edges.get(i));
		}
	}

	public void addEdge(int from, int to) {
		new Edge(nodes.get(from - 1), nodes.get(to - 1));
	}

	public int depthFirstSearch(BinaryTree<Integer> visitTree,
			ArrayList<GraphNode> startNodes, BinaryTree<Integer> cycleNodes,
			GraphNode current) {
		int k = -1;
		current.setVisited(true);
		visitTree.delete(current.getContent());

		if (current.getInDegree() == 0) {
			startNodes.add(current);
		}

		for (int i = 0; i < current.getEdges().size(); i++) {
			if (!current.getEdges().get(i).isVisited()) {
				GraphNode adjacent;
				if (i == 0)
					adjacent = current.getEdges().get(i).getTo();
				else
					adjacent = current.getEdges().get(i).getFrom();
				current.getEdges().get(i).setVisited(true);
				if (!adjacent.isVisited()) {
					int m = depthFirstSearch(visitTree, startNodes, cycleNodes,
							adjacent);
					if (m > 0) {
						k = m;
					}
				} else {
					k = adjacent.getContent();
				}
			}
		}

		if (k != -1) {
			cycleNodes.add(current.getContent());
		}
		if (k == current.getContent()) {
			k = -1;
		}
		return k;
	}

	public long findIdempotent() {
		ArrayList<Integer> visit = new ArrayList<Integer>();
		for (int i = 1; i <= this.nodes.size(); i++) {
			visit.add(i);
		}
		int distanceToCycle = 1;
		ArrayList<Integer> sizeOfCyles = new ArrayList<Integer>();
		BinaryTree<Integer> visitTree = new BinaryTree<Integer>(
				Integer.MAX_VALUE, visit);
		while (visitTree.size() > 0) {
			BinaryTree<Integer> cycleNodes = new BinaryTree<Integer>(
					Integer.MAX_VALUE);
			ArrayList<GraphNode> startNodes = new ArrayList<GraphNode>();
			depthFirstSearch(visitTree, startNodes, cycleNodes,
					this.nodes.get(visitTree.peek() - 1));
			sizeOfCyles.add(cycleNodes.size());
			while (!startNodes.isEmpty()) {
				int distance = 1;
				GraphNode mover = startNodes.remove(startNodes.size() - 1);
				while (true) {
					if (cycleNodes.contains(mover.getOutGoing().getTo()
							.getContent())) {
						break;
					}
					distance++;
					mover = mover.getOutGoing().getTo();
				}
				if (distance > distanceToCycle) {
					distanceToCycle = distance;
				}
			}
		}
		long lcm = sizeOfCyles.remove(sizeOfCyles.size() - 1);
		while (sizeOfCyles.size() > 0) {
			lcm = Main.lcm(lcm, sizeOfCyles.remove(sizeOfCyles.size() - 1));
		}
		return (long) (Math.ceil((double) distanceToCycle / lcm)) * lcm;
	}
}

class BinaryTree<T extends Comparable<T>> {
	private Node<T> header;
	private int numberOfElements;

	public BinaryTree(T header) {
		this.header = new Node<T>(header);
		numberOfElements = 0;
	}

	public BinaryTree(T header, ArrayList<T> list) {
		this(header);
		this.header.setLeftChild(sortedListToTree(0, list.size() - 1, list));
	}

	public int size() {
		return this.numberOfElements;
	}

	public Node<T> getHeader() {
		return this.header;
	}

	public void print(Node<T> a) {
		if (a != null) {
			print(a.getLeftChild());
			System.out.println(a.getContent());
			print(a.getRightChild());
		}
	}

	private Node<T> sortedListToTree(int left, int right, ArrayList<T> list) {
		Node<T> ret = null;
		if (left <= right) {
			int middle = (left + right) / 2;
			ret = new Node<T>(list.get(middle));
			ret.setLeftChild(sortedListToTree(left, middle - 1, list));
			ret.setRightChild(sortedListToTree(middle + 1, right, list));
		}
		this.numberOfElements = list.size();
		return ret;
	}

	public void add(T add) {
		Node<T> rear = null;
		Node<T> front = this.header;
		boolean leftOrRight = true;
		while (front != null) {
			if (add.compareTo(front.getContent()) > 0) {
				rear = front;
				front = front.getRightChild();
				leftOrRight = false;
			} else if (add.compareTo(front.getContent()) < 0) {
				rear = front;
				front = front.getLeftChild();
				leftOrRight = true;
			} else {
				break;
			}
		}
		if (leftOrRight) {
			rear.setLeftChild(new Node<T>(add));
		} else {
			rear.setRightChild(new Node<T>(add));
		}
		this.numberOfElements++;
	}

	public boolean contains(T search) {
		if (find(search) != null) {
			return true;
		} else {
			return false;
		}
	}

	public Node<T> find(T key) {
		Node<T> found = null, mover = this.header;
		while (mover != null) {
			if (key.compareTo(mover.getContent()) > 0) {
				mover = mover.getRightChild();
			} else if (key.compareTo(mover.getContent()) < 0) {
				mover = mover.getLeftChild();
			} else {
				found = mover;
				break;
			}
		}
		return found;
	}

	public void delete(T deleteNum) {
		Node<T> mover = this.header;
		Node<T> backMover = null;
		while (mover != null) {
			if (deleteNum.equals(mover.getContent())) {
				break;
			} else if (deleteNum.compareTo(mover.getContent()) == -1) {
				backMover = mover;
				mover = mover.getLeftChild();
			} else {
				backMover = mover;
				mover = mover.getRightChild();
			}
		}

		Node<T> replace = null;
		Node<T> backReplace = null;

		if (mover.getLeftChild() != null) {
			replace = mover.getLeftChild();
			while (replace.getRightChild() != null) {
				backReplace = replace;
				replace = replace.getRightChild();
			}
			if (backReplace != null) {
				backReplace.setRightChild(replace.getLeftChild());
				replace.setLeftChild(mover.getLeftChild());
			}
			replace.setRightChild(mover.getRightChild());
		} else if (mover.getRightChild() != null) {
			replace = mover.getRightChild();
			while (replace.getLeftChild() != null) {
				backReplace = replace;
				replace = replace.getLeftChild();
			}
			if (backReplace != null) {
				backReplace.setLeftChild(replace.getRightChild());
				replace.setRightChild(mover.getRightChild());
			}
			replace.setLeftChild(mover.getLeftChild());
		}

		if (mover.getContent().compareTo(backMover.getContent()) == -1) {
			backMover.setLeftChild(replace);
		} else {
			backMover.setRightChild(replace);
		}
		this.numberOfElements--;
	}

	public T pop() {
		T temp = this.header.getLeftChild().getContent();
		delete(temp);
		return temp;
	}

	public T peek() {
		return this.header.getLeftChild().getContent();
	}
}

class Edge {
	private GraphNode from;
	private GraphNode to;
	private boolean visited;

	public Edge(GraphNode from, GraphNode to) {
		this.from = from;
		this.to = to;
		this.visited = false;
		from.addOutGoingEdge(this);
		to.addEdgeToInComes(this);
	}

	public GraphNode getFrom() {
		return from;
	}

	public void setFrom(GraphNode from) {
		this.from = from;
	}

	public GraphNode getTo() {
		return to;
	}

	public void setTo(GraphNode to) {
		this.to = to;
	}

	public boolean isVisited() {
		return visited;
	}

	public void setVisited(boolean visited) {
		this.visited = visited;
	}

}

class Node<T> {
	private T content;
	private Node<T> rightChild;
	private Node<T> leftChild;

	public Node<T> getRightChild() {
		return rightChild;
	}

	public void setRightChild(Node<T> rightChild) {
		this.rightChild = rightChild;
	}

	public Node<T> getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(Node<T> leftChild) {
		this.leftChild = leftChild;
	}

	public Node(T content) {
		super();
		this.content = content;
	}

	public T getContent() {
		return content;
	}

	public void setContent(T content) {
		this.content = content;
	}

}