Mr. Yagami is playing a game of arrays. He is given two random arrays A and B consisting of N positive integer elements. Game starts by Mr. Yagami assigning 0 or 1 to each element in A and B.

After this assignment is done, a graph is constructed with a node for each element in the array A and B (2N nodes) and no edges. The game proceeds with a valid move being defined in the following way:

• One of the arrays from A or B is selected. From the selected array, an element which has been marked 0 is chosen. Let us call this element as X.
• A set of elements, Y, are chosen from the array, which was not chosen in the first step, such that all elements of Y should be marked as 1 and all elements of Y should be greater than X and no element of Y should be coprime to X.
• Finally an edge is drawn from the node labelled X to all the nodes corresponding to the elements in set Y. There can only be a single edge between any 2 nodes in the graph.

He can make as many valid moves. Mr. Yagami receives 1 point for each edge that is drawn in the graph.

Mr. Yagami is very clever, so he makes the initial assignment in such a way that it maximizes the number of points he receives in the game. You have to return the maximum number of points that Mr. Yagami can receive.

Input

The first line of the input contains a single integer, N (1 ≤ N ≤ 40)

The second line of input contains N integers separated by a single space character, which represent the elements of the array A. (2 ≤ A[i] ≤ 10^9)

Similarly, the last line of input also contains N integers separated by a single space character, which represent the elements of the array B. (2 ≤ B[i] ≤ 10^9)

Output

A single integer representing the maximum score which Mr. Yagami can receive.

Sample

Input:
4
16 3 2 9
12 18 13 4

Output:
8

Explanation

• He picks 2 from first array. So he gets to put 3 edges i.e. 2→4, 2→12, 2→18.
• Next he picks 3 from the first array. So he gets to put 2 edges i.e. 3→12, 3→18.
• Next he picks 9 from the first array. So he gets to put 2 edges i.e. 9→12, 9→18.
• Next he picks 16 from the first array. So he gets to put 1 edge i.e. 16→18. Total edges = 8.

Problem Setter: Lalit Kundu