Sophia is playing a game on the computer. There are two random arrays A & B, each having the same number of elements. The game begins with Sophia removing a pair (Ai, Bj) from the array if they are not co-prime. She keeps a count on the number of times this operation is done.

Sophia wants to find out the maximal number of times(S) she can do this on the arrays. Could you help Sophia find the value?

Input Format

The first line contains an integer n. 2 lines follow, each line containing n numbers separated by a single space. The format is shown below.

n
A[0] A[1] ... A[n - 1]
B[0] B[1] ... B[n - 1]

Constraints

0 < n <= 105
2 <= A[i], B[i] <= 109
Each element in both arrays are generated randomly between 2 and 109

Output Format

Output S which is the maximum number of times the above operation can be made.

Sample Input

4
2 5 6 7
4 9 10 12

Sample Output

3

Explanation

You can remove:

(2, 4)
(5, 10)
(6, 9)

hence 3.

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score