Problem Statement

Aoki is playing with a sequence of numbers $a_{1}, a_{2}, ..., a_{N}$. Every second, he performs the following operation :

• Choose a positive integer $k$. For each element of the sequence $v$, Aoki may choose to replace $v$ with its remainder when divided by $k$, or do nothing with $v$. The cost of this operation is $2^{k}$ (regardless of how many elements he changes).

Aoki wants to turn the sequence into $b_{1}, b_{2}, ..., b_{N}$ (the order of the elements is important). Determine if it is possible for Aoki to perform this task and if yes, find the minimum cost required.

Constraints

• $1 \leq N \leq 50$
• $0 \leq a_{i}, b_{i} \leq 50$
• All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N
a_{1} a_{2} ... a_{N}
b_{1} b_{2} ... b_{N}

Output

Print the minimum cost required to turn the original sequence into $b_{1}, b_{2}, ..., b_{N}$. If the task is impossible, output $-1$ instead.