解题思路

设数组中的最小值为 $mn$。

取模操作有一个重要性质：若当前值为 $y$，对 $b$ 取模后：

• 若 $y < b$，则 $y \bmod b = y$，结果不变；
• 若 $y \ge b$，则 $y \bmod b < b$，结果会严格变小。

题目内容

笨蛋同学拿到了一个正整数数组 $a$，以及一个初始数字$x$。她准备进行一次 “取模仪式”： 她可以把数组 $a$重新排列成任意一个排列 $b_1, b_2, \dots, b_n$（即把所有元素按某种顺序依次使用一次），然后从 $y_0 = x$ 开始，按顺序执行： $y_i = y_{i-1} \bmod b_i \quad (1 \le i \le n)$其中 $mod$ 表示取模运算。仪式结束后得到最终结果 $y_n$。 现在她希望最终结果尽可能大。请你输出所有排列 $b$ 中可能得到的最大 $y_n$。

输入描述

每个测试文件均包含多组测试数据。

• 第一行输入一个整数

  $T\ (1 \le T \le 2 \times 10^5)$

  代表数据组数，每组测试数据描述如下：

  • 第一行输入两个整数 $n, x\ (1 \le n \le 2 \times 10^3,\ 0 \le x \le 10^{18})$。
  • 第二行输入$n$ 个正整数 $a_1, a_2, \dots, a_n\ (1 \le a_i \le 2 \times 10^3)$。

保证单个测试文件中所有测试数据的$n$ 之和不超过 $5 \times 10^3$。

输出描述

对于每组测试数据，输出一行一个整数，表示可能得到的最大 $y_n$。

样例1

输入

2
3 20
5 6 8
5 37
7 13 6 10 4

输出

4
3

说明

第一组：取排列 $(8, 6, 5)$：$20 \bmod 8 = 4$，之后对 $6, 5$ 取模不会改变结果，最终得到 $4$，这是最大值。

第二组：通过最优排列，最终可以得到的最大值为 $3$。