Recently Deltaforces, a famous competitive programming website, added a lot of new visual information to user profiles. In particular, there is a maximum day streak — the maximum number of days in a row with at least one problem solved. You decided that the maximum day streak in your profile does not accurately represent your training efforts. So you came up with a thought — what if you could change the time zone in your profile to increase the maximum day streak?
Let's formalize this setting as follows. Suppose you have solved n problems, and the i-th problem was solved at time ai. There are m time zones, numbered from 0 to m−1. The default time zone is 0. If you decide to change your time zone to t, all solutions' timestamps increase by t: the problem solved at time ai is now considered to be solved at time ai+t, for all i simultaneously.
The problem solved at time x is considered to be solved on day number ⌊mx⌋. Here ⌊v⌋ means v rounded down to the greatest integer less than or equal to v.
To display the maximum day streak, Deltaforces finds such l and r that you have solved at least one problem on each of days l,l+1,…,r, and r−l+1 is as large as possible. Then your maximum day streak is shown as r−l+1.
Find the maximum day streak you can achieve by selecting a time zone.
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤2⋅105). Description of the test cases follows.
The first line of each test case contains two integers n and m — the number of solved problems and the number of time zones (1≤n≤2⋅105; 1≤m≤109). The second line contains n integers a1,a2,…,an — distinct timestamps of your solutions, in chronological order (0≤a1<a2<⋯<an≤109).
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
For each test case, print two integers s and t — the maximum day streak and any time zone that achieves it (1≤s≤n; 0≤t<m).
In the first example test case, when you select time zone 2, the timestamps of your solutions change to 2, 5, 10, and 26. It means the problems are now considered to be solved on days 0, 0, 1, and 2; that is a 3-day streak. Time zones 3, 4, and 5 yield the same answer.
In the second example test case, timestamps of your solutions are 37 and 40 in time zone 5, which corresponds to days 3 and 4. Time zones 6 and 7 also work.
In the third example test case, only one time zone exists, and your maximum day streak is 5.
In the fourth example test case, you have solved many problems but in a short period of time, and you can't obtain more than a 2-day streak.