Fish was retired from programming, and now he goes back home and runs a shop.
There are $N$ kinds of goods in sale in his shop, and the $i$-th goods will be sold exactly $x_i$ pieces everyday. However, as his inventory shelf has a fixed and limited volume $V$, he has to manage the distribution of these goods. To do so, he wants to assign a real value $v_i$ to $i$-th goods as its maximum quantity storing in the shelf such that $sum v_i = V$. When one kind of goods is sold out, he can refill the shelf with this goods to its maximum quantity. As a result, for $i$-th goods, he will refill $frac(x_i, v_i)$ times per day.
Please help Fish determine the $v_i$ for all goods so that the number of times he use to refill all the goods everyday is minimum.
The first line of input contains an integer $T$, representing the number of test cases.
Then for each test case:
The first line contains two integers $N, V$ as mentioned above.
The second line contains $N$ integers $x_1, x_2, \\\\cdots, x_N$ as mentioned above.
All numbers in the same line are separated by one space.
For each test case, you should output *Case $x$: $y$*, where $x$ indicates the case number starting from $1$, and $y$ is the minimum number of times he refills the goods of all kinds in one day.
Your answer will be considered correct if its absolute error does not exceed $10^(-6)$.
$1 <= T <= 100$
$1 <= N <= 10^5$
$1 <= V <= 10^9$
For $90 %$ test cases: $N <= 100$
## Input
The first line of input contains an integer $T$, representing the number of test cases.Then for each test case:The first line contains two integers $N, V$ as mentioned above.The second line contains $N$ integers $x_1, x_2, \\\\cdots, x_N$ as mentioned above.All numbers in the same line are separated by one space.
## Output
For each test case, you should output *Case $x$: $y$*, where $x$ indicates the case number starting from $1$, and $y$ is the minimum number of times he refills the goods of all kinds in one day.Your answer will be considered correct if its absolute error does not exceed $10^(-6)$.
[samples]
## Note
$1 <= T <= 100$$1 <= N <= 10^5$$1 <= V <= 10^9$For $90 %$ test cases: $N <= 100$
**Definitions**
Let $ \mathbf{v} = (x, y) \in \mathbb{Z}^2 $ be a 2D integer vector.
Let $ \|\mathbf{v}\|_2 = \sqrt{x^2 + y^2} $ denote the Euclidean norm.
**Constraints**
1. $ 1 \leq Q \leq 10^6 $
2. For each query $ i $, $ |x_i|, |y_i| \leq 10^6 $, and $ (x_i, y_i) \in \mathbb{Z}^2 $
**Objective**
For each query $ (x, y) $, compute the number of nonempty sequences of vectors $ \{\mathbf{a}_i\}_{i=0}^n $ (for some $ n \geq 0 $) such that:
- $ \mathbf{a}_0 = \mathbf{0} $,
- $ \mathbf{a}_n = (x, y) $,
- For all $ i \in \{1, \dots, n\} $, $ \|\mathbf{a}_i - \mathbf{a}_{i-1}\|_2 \in \mathbb{Z} $,
- The sequence is strictly increasing in norm: $ \|\mathbf{a}_i\|_2 < \|\mathbf{a}_{i+1}\|_2 $ for all $ i < n $.
Let $ f(x, y) $ be the number of such sequences for vector $ (x, y) $.
Output $ f(x_i, y_i) \mod (10^9 + 7) $ for each query $ i $.