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
#include <iostream>
using namespace std;
const int lim = 50;
int n, a[55], b[55]; long long c[55]; bool dp[55][55][55];
int main() {
	for (int i = 0; i <= lim; i++) dp[0][i][i] = true;
	for (int i = 1; i <= lim; i++) {
		for (int j = 0; j <= lim; j++) {
			for (int k = 0; k <= j; k++) {
				dp[i][j][k] = dp[i - 1][j][k] || dp[i - 1][j % i][k];
			}
		}
	}
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i], c[i] = 1LL << a[i];
	for (int i = 0; i < n; i++) cin >> b[i];
	bool feasible = true;
	for (int i = 0; i < n; i++) feasible = feasible && dp[lim][a[i]][b[i]];
	if (!feasible) cout << "-1\n";
	else {
		long long ret = 0;
		for (int i = lim; i >= 1; i--) {
			bool change = false;
			for (int j = 0; j < n; j++) {
				bool unchange = false;
				for (int k = 0; k <= lim; k++) {
					if (dp[i - 1][k][b[j]] && ((c[j] >> k) & 1)) {
						unchange = true;
					}
				}
				if (!unchange) change = true;
			}
			if (change) {
				for (int j = 0; j < n; j++) {
					for (int k = i; k <= lim; k++) {
						if ((c[j] >> k) & 1) c[j] |= 1LL << (k % i);
					}
				}
				ret |= 1LL << i;
			}
		}
		cout << ret << "\n";
	}
	return 0;
}