You are given two arrays \(A\) and \(B\) of \(N\) integers each.  For each pair \((i, j)\) with \(1 \leq i < j \leq N\) we compute \(\gcd(A_i, A_j) + \gcd(B_i, B_j)\). What is the maximum possible such value and for how many pairs does it occur?

Input

The first line contains an integer \(N\).

The second line contains \(N\) integers, representing \(A\).

The third line contains \(N\) integers, representing \(B\).

Output

Print the answers on a single line, separated by space.

Notes and contraints

\(2 \leq N \leq 10^5\)

\(1 \leq A_i, B_i \leq 10^5 \ \forall\ 1 \leq i \leq N\)

For 20 points, \(N \leq 10^3\).