A. Ya Sabah El GCD
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$, each of length $$$n$$$ ($$$1 \le n \le 5000$$$). You may perform the following operation any number of times (indices are 1-based):

  • Choose an index $$$i$$$ ($$$1 \le i \le n$$$) and set $$$a[i] := \gcd(a[i], b[i])$$$. The cost of performing this operation at index $$$i$$$ is $$$i^2 + i$$$.

Your task is to compute the minimum total cost required to make the gcd of all elements of array $$$a$$$ equal to $$$1$$$. If it is impossible to achieve $$$\gcd(a[1], a[2], \ldots, a[n]) = 1$$$ by any sequence of operations, print $$$-1$$$.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a[i] \le 10^{12}$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b[i] \le 10^{12}$$$).

Output

Print a single integer — the minimum total cost to make $$$\gcd(a_1, a_2, \ldots, a_n) = 1$$$, or $$$-1$$$ if it is impossible.

Examples
Input
2
6 10
3 7
Output
2
Input
3
6 30 60
5 10 21
Output
2