「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 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
提示
请注意输入输出上的优化！
通知
比赛状态发生变化，点 OK 刷新。
通知