在一次实验课程中，研究员奶龙大王正在研究“整数共振强度”的测量方式。 
对于一个正整数 x，它定义了共振强度函数：

•  g(x) = 2^w(x) 其中 w(x) 表示 x 的不同质因子个数。 

例如：  

• 12 = 2^2 * 3，包含质因子 2 和 3，因此 w(12)=2，g(12)=4； 
• 30 = 2 * 3 * 5，包含质因子 2, 3, 5，因此 w(30)=3，g(30)=8。 

研究员 奶龙大王 的两位助手分别准备了两个长度均为 n 的整数序列：  

• 助手贝利亚大帝给出了序列 a 
• 助手笨蛋噜噜给出了序列 b 

研究中需要对序列 a 进行重新排列，得到新的序列 c。 
随后计算以下共振总强度： 
Sum = g(c_1 + b_1) + g(c_2 + b_2) + ... + g(c_n + b_n)
目标是最大化这个值。 
你的任务是找出最佳排列方式，并输出能达到的最大共振总强度。 

本题单个测试点内含多组数据。

第一行输入整数 T (1 <= T <= 10)，表示测试组数。

对每组数据：

第一行输入整数 n (1 <= n <= 8)；

第二行输入 n 个整数 a_1 ... a_n (1 <= a_i <= 10^4)；

第三行输入 n 个整数 b_1 ... b_n (1 <= b_i <= 10^4)。

对于每组数据，输出一行一个整数，即最大化后的共振总强度。

第一组数据：

n = 3，a = {1, 2, 3}，b = {4, 5, 6}。

一种最优的排列是将 a 重排为 c = {2, 1, 3}。

此时对应的求和过程如下：

1. c[1]=2, b[1]=4 -> 和为 6。

   6 = 2 * 3，有两个不同质因子 (2, 3)，所以 g(6) = 2^2 = 4。

2. c[2]=1, b[2]=5 -> 和为 6。

   6 = 2 * 3，有两个不同质因子 (2, 3)，所以 g(6) = 2^2 = 4。

3. c[3]=3, b[3]=6 -> 和为 9。

   9 = 3 * 3，只有一个不同质因子 (3)，所以 g(9) = 2^1 = 2。

总共振强度 = 4 + 4 + 2 = 10。

第二组数据：

n = 3，a = {1, 2, 3}，b = {3, 4, 5}。

一种最优的排列是将 a 重排为c = {3, 2, 1}。

此时对应的求和过程如下：

1. c[1]=3, b[1]=3 -> 和为 6，g(6) = 4。

2. c[2]=2, b[2]=4 -> 和为 6，g(6) = 4。

3. c[3]=1, b[3]=5 -> 和为 6，g(6) = 4。

总共振强度 = 4 + 4 + 4 = 12。

 "黑马程序员杯"郑州经贸学院程序设计大赛