← 返回题目列表

Codeforces · 2008/G

G. 樱子的任务

中文机器翻译题面 查看原题

樱子给你准备了一个任务:

她给你一个$$$n$$$整数数组,并允许你选择$$$i$$$和$$$j$$$,使得$$$i \neq j$$$和$$$a_i \ge a_j$$$,然后分配$$$a_i = a_i - a_j$$$或$$$a_i = a_i + a_j$$$。您可以对任何 $$$i$$$ 和 $$$j$$$ 执行此操作任意次,只要它们满足条件即可。

Sakurako 问你经过任意次数的操作后,数组的 $$$mex_k$$$$$$^{\text{∗}}$$$ 的最大可能值是多少。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\le n\le 2\cdot 10^5,1\le k\le 10^9$$$) — 数组中元素的数量以及 $$$mex_k$$$ 的值 $$$k$$$。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出通过操作可以达到的最大$$$mex_k$$$。

示例

输入 #1

6
1 3
3
2 10
1 1
3 1
1 2 3
3 2
1 2 4
4 5
2 2 2 16
4 5
2 2 2 3

输出 #1

2
11
3
4
8
8