该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

谁说站在光里的才算英雄

Description

小马最讨厌做数学题了，但是队长 \(yjj\) 经常把数学题丢给她做，她不得已只能买了xx算法竞赛专题班——数学进行学习。
有一天，小马在看xx算法竞赛专题班——数学第二章同余与模的时候睡着了，这时候被走进来的 \(yjj\) 看到了，\(yjj\) 为了惩罚摸鱼的小马，给她施了一个魔法，只有她在梦中解决了 \(yjj\) 给的关于模数的问题，小马才能醒过来。
关于 \(yjj\) 的问题是这样的：
\(yjj\) 给了小马两个长度为 \(n\) 的序列 \(a, \ b\)。小马可以选择一个数字 \(k\)，选择的费用为 \(2^k\)，并进行一次如下操作：

• 对于序列 \(a\) 的每个元素，小马可以选择用 \(a_i \% \ k\) 来修改 \(a_i\)，也可以不修改。

小马需要知道把序列 \(a\) 变成序列 \(b\) 所需要的最小费用是多少，如果不能把序列 \(a\) 变成序列 \(b\)，答案就是 \(-1\)。

由于小马实在太菜了，她托梦向你求救，请你告诉小马答案，帮助小马逃脱队长 \(yjj\) 的惩罚。

Format

Input

第一行输入一个正整数 \(T\)，表示有 \(T\) 次询问。
接下来输入 \(3 \times T\) 行。
对于每次询问，第一行输入 \(n\)，表示序列的长度。
第二行输入 \(n\) 个数，表示序列 \(a\)。
第三行输入 \(n\) 个数，表示序列 \(b\)。

对于 \(100 \%\) 数组，\(1\leq T \leq 10\)，\(1\leq n \leq 50\)，\(0 \leq a_i,\ b_i \leq 50\)

Output

对于每次询问，在一行内输出把序列 \(a\) 变成序列 \(b\) 所需要的最小费用

Sample 1

Input

1
3
19 10 14
0 3 4

Output

160

Limitation

1s, 1024KiB for each test case.