题目内容

小华获得了一组共 $n$ 个能量调节器，每个调节器有一个正整数参数，还带有一个初始能量值 $x$。她必须将所有调节器按某种顺序使用恰好一次：每次使用一个参数为 $a$ 的调节器后，能量值变为当前能量值对 $a$ 取模的结果。她希望经过全部 $n$ 次操作后，最终剩余的能量值尽可能大。

请你帮助她计算：在所有可能的调节器使用顺序中，最终能量值的最大可能值是多少。

约束条件：调节器数量 $n$ 不超过 2000，所有调节器参数均为不超过 2000 的正整数，初始能量值 $x$ 不超过 10^{18}。测试数据组数 $T$ 最多为 2×10^5，且所有测试数据的 $n$ 之和不超过 5000。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。接下来每组测试数据按以下格式给出： 第一行包含两个整数 $n$ 和 $x$，分别表示调节器的数量和初始能量值。 第二行包含 $n$ 个正整数，表示每个调节器的参数。

输出描述

对于每组测试数据，输出一行一个整数，表示最终可能获得的最大剩余能量值。

样例1

输入

1
2 10
12 15

输出

10

说明

该组数据中初始能量值 $x = 10$，调节器参数为 $12$ 和 $15$，最小值为 $12$。由于 $x < 12$，无论以何种顺序使用调节器，当前能量始终小于所有调节器参数，因此每一次取模操作都不会改变能量值。最终剩余能量即为初始值 $10$。

样例2

输入

1
4 100
7 9 11 13

输出

2

说明

调节器参数中的最小值为 $mn = 7$，初始能量 $x = 100 \ge 7$。为了得到尽可能大的最终能量，我们需要在所有可达状态中找出小于 $7$ 的最大值。

一种可行的操作顺序为：先用参数为 $13$ 的调节器，能量变为 $100 \bmod 13 = 9$；再用参数为 $7$ 的调节器，能量变为 $9 \bmod 7 = 2$；剩下的调节器参数 $9$ 和 $11$ 均大于当前能量 $2$，操作后能量保持 $2$ 不变。若先使用参数 $7$，能量直接从 $100$ 变为 $2$，之后也不再改变。经过搜索，所有可达的小于 $7$ 的状态为 $\{0, 1, 2\}$，其中最大值为 $2$，因此答案为 $2$。

样例3

输入

2
1 5
10
3 29
5 7 11

输出

5
4

说明

该测试用例包含两组数据。

第一组：只有一个调节器，参数为 $10$。初始能量 $x = 5 < 10$，取模不改变能量，最终剩余 $5$。

第二组：初始能量 $x = 29$，调节器参数为 $5, 7, 11$，最小值 $mn = 5 \le 29$。考虑可达状态：若先使用参数 $5$，能量直接变为 $29 \bmod 5 = 4$；之后 $7$ 和 $11$ 均大于 $4$，结果保持 $4$。若先使用 $11$，能量变为 $29 \bmod 11 = 7$；再用 $5$，能量变为 $7 \bmod 5 = 2$；最后 $7$（或 $11$）不再改变结果，得到 $2$。所有可达状态为 $\{1, 2, 4, 7\}$，其中小于 $5$ 的最大值为 $4$，故输出 $4$。