Epsilon Estuary

题号：NC295145
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

Recently Colin got addicted to playing a tactics puzzle RPG: Super Algebrawl. In the game, Colin transforms into a boar king with magical mathematical powers! He is on a quest for glory, slaying the horrible monsters that plague the animal realm. Every encounter is a puzzle to be solved with logic and simple algebra!

Just now, Colin came to the next battlefield: Epsilon Estuary. The slimes are the rulers here, and they have a disgusting splitting skill - "SPLASH": once it is injured, assuming its remaining health is $x$ , it will immediately split into two slimes with health $\lfloor x/2\rfloor$ and $\lceil x/2 \rceil$ respectively, and the new slimes can continue to use this skill if they are injured in the future. A slime with health $0$ will die immediately.

However, our challenger Colin happens to have the best weapon against them: the "SHOCK" magic scroll! Specifically, every time Colin uses the shock magic scroll, it will inflict $y$ damage to every monster. If a monster's health does not exceed $y$ before Colin uses the magic scroll, it will die immediately after Colin uses the magic scroll.

The image above shows an example: assuming $y=5$ , and there are two slimes on the field with health values $x_1=25,\ x_2=8$ . After Colin used the scroll once, their health became $x_1'=20,\ x_2'=3$ respectively. Then they split immediately. The first slime split into two slimes with health $10$ and $10$ respectively; the second slime split into two slimes with health $2$ and $1$ respectively.

Colin's magic scroll can be used any number of times, so this is destined to be a one-way killing. But clicking the mouse repeatedly is too tiring, so Colin would like you to calculate, given the initial status of the slimes on the field, how many times does he need to use the scroll at least to ensure that all monsters on the field are killed?

输入描述:

The first line contains a single integer , representing the number of test cases.

For each test case:

The first line contains two integers , representing the number of slimes on the battlefield and the damage can be made to each slime by using the magic scroll once.

The second line contains  integers , representing the initial health of each slime on the battlefield.

It's guaranteed that the sum of  over all the test cases will not exceed .

输出描述:

Output  lines, the -th line contains a single integer, representing the answer for the -th test case.

示例1

输入

复制

输出

复制

3
7

说明

For the first test case, the changes in health of the slimes on the field are: