3250. 计软联谊

Time limit per test: 7.0 seconds

Memory limit: 512 megabytes

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

友谊度 是这么计算的:令 , 两个整数分别是两个同学的属性,两个同学的友谊度取决于 大的公约数。如果不存在,就说明这两个同学之间完全没有友谊,友谊度为

Input

第一行是数据组数

对于每组数据:
第一行:首先是学生的数量 ,约定的常数
第二行: 个整数,依次表示这些学生的属性值:

Output

对于每组数据输出一行,以 Case x: 开头(x 表示数据编号,从 1 开始),后面是 个整数,分别是 ,整数和整数之间用空格隔开。

Examples

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

Note

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

57 Solved out of 156 users tried.

78 Accepted out of 690 tried.

5.9 EMB will be rewarded for solving this problem.

Created: 1 year, 2 months ago.

Updated: 7 months, 2 weeks ago.

Latest Submission: 2 months ago.

Source: 2017 华东师范大学校赛

Problem Tags