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.

Examples

Input

3
19 10 14
0 3 4

Output

160

Input

3
19 15 14
0 0 0

Output

2

Input

2
8 13
5 13

Output

-1

Input

4
2 0 1 8
2 0 1 8

Output

0

Input

1
50
13

Output

137438953472

见题面

见题面