#MMWX14. Hide

Hide

Description

构造正整数 nn。给定一个长度为 mm 的序列 aa,满足 gcd⁡(a1,am)=1\gcd(a_1 , a_m) = 1。同时输入一个序列 bi=ngcd⁡(n,ai)b_i = \dfrac{n}{\gcd(n,a_i)}。请求出正整数 nn,或报告无解。

有解的话 n≤1018n \leq 10^{18}。

Constraints and Subtasks

对于全部测试点,满足:

  • 1≤n≤10181 \leq n \leq 10^{18},如果有解的话。
  • 2≤m≤2×1052 \leq m \leq 2 \times 10^5
  • 1≤T≤2×1051 \leq T \leq 2 \times 10^5
  • ∑m≤2×105\sum m \leq 2 \times 10^5
  • 1≤ai,bi≤10181 \leq a_i,b_i \leq 10^{18}
  • 所有输入数字均为整数。

另外,还有一些测试点满足特殊要求。

分值 n≤n \leq ∑m≤\sum m \leq 特殊性质
25%25\% 10001000 10001000
25%25\% 2×1052\times10^5 m=10000m = 10000 aia_i 从值域内随机生成
50%50\% 101810^{18} 2×1052\times10^5

Input

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

输入内容从标准输入给出。先读入数据组数 TT。

对于每组数据,格式如下:

$ \boxed{\begin{aligned} & m \\ & a_1 \quad a_2 \quad \dots \quad a_m \\ & b_1 \quad b_2 \quad \dots \quad b_m \end{aligned}} $

Output

对于每组数据,输出一个正整数表示答案,无解输出 −1-1。

Samples

1
3
1 2 3
1 1 1
1