「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (重现)

K. 计软联谊

单点时限: 7.0 sec

内存限制: 512 MB

在计算机和软件专业的联谊会上,计算机和软件的同学相间着排成一列。现在要计算相邻两个同学的友谊度。

友谊度 $\mathrm{friend}(a, b)$ 是这么计算的:令 $a$, $b$ 两个整数分别是两个同学的属性,两个同学的友谊度取决于 $a, b$ 第 $k$ 大的公约数。如果不存在,就说明这两个同学之间完全没有友谊,友谊度为 $-1$。

输入格式

第一行是数据组数 $T$ $(1 \leq T \leq 70)$。

对于每组数据:
第一行:首先是学生的数量 $n$ $(1 \leq n \leq 10^5)$,约定的常数 $k$ $(1 \leq k \leq 10^6)$。
第二行:$n$ 个整数,依次表示这些学生的属性值:$m_1, m_2, \ldots, m_n$ $(1 \leq m_i \leq 10^6)$。

输出格式

对于每组数据输出一行,以 Case x: 开头(x 表示数据编号,从 1 开始),后面是 $n-1$ 个整数,分别是 $\mathrm{friend}(m_1, m_2), \mathrm{friend}(m_2, m_3), \ldots, \mathrm{friend}(m_{n-1}, m_n)$,整数和整数之间用空格隔开。

样例

Input
2
3 1
4 6 12
6 2
13 12 12 24 36 30
Output
Case 1: 2 6
Case 2: -1 6 6 6 3

提示

请注意输入输出上的优化!