You are given an array $a$ of length $n$, and an integer $x$. You can perform the following operation as many times as you would like (possibly zero): replace two adjacent elements of the array by their sum. For example, if the initial array was $[3, 6, 9]$, in a single operation one can replace the last two elements by their sum, yielding an array $[3, 15]$, or replace the first two elements to get an array $[9, 9]$. Note that the size of the array decreases after each operation.

The beauty of an array $b=[b_1, \ldots, b_k]$ is defined as $\sum_{i=1}^k \left\lceil \frac{b_i}{x} \right\rceil$, which means that we divide each element by $x$, round it up to the nearest integer, and sum up the resulting values. For example, if $x = 3$, and the array is $[4, 11, 6]$, the beauty of the array is equal to $\left\lceil \frac{4}{3} \right\rceil + \left\lceil \frac{11}{3} \right\rceil + \left\lceil \frac{6}{3} \right\rceil = 2 + 4 + 2 = 8$.

Please determine the minimum and the maximum beauty you can get by performing some operations on the original array.

The first input line contains a single integer $t$ — the number of test cases ($1 \le t \le 1000$).

The first line of each test case contains two integers $n$ and $x$ ($1 \leq n \leq 10^5$, $1 \leq x \leq 10^9$).

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$), the elements of the array $a$.

It is guaranteed that the sum of values of $n$ over all test cases does not exceed $10^5$.

For each test case output two integers — the minimal and the maximal possible beauty.