Finally, a COVID vaccine is out on the market and the Chefland government has asked you to form a plan to distribute it to the public as soon as possible. There are a total of N$N$ people with ages a1,a2,…,aN$a_1,a_2,\dots ,a_N$.

There is only one hospital where vaccination is done and it is only possible to vaccinate up to D$D$ people per day. Anyone whose age is ≥80$\ge 80$ or ≤9$\le 9$ is considered to be at risk. On each day, you may not vaccinate both a person who is at risk and a person who is not at risk. Find the smallest number of days needed to vaccinate everyone.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains two space-separated integers N$N$ and D$D$.
• The second line contains N$N$ space-separated integers a1,a2,…,aN$a_1,a_2,\dots ,a_N$.

Output

For each test case, print a single line containing one integer ― the smallest required number of days.

Constraints

• 1≤T≤10$1\le T\le 10$