思路

这个问题可以分解为两个主要步骤：

1. 高效计算每个数字的重量。
2. 在计算出的重量序列上，寻找长度不超过 $k$ 的最大连续子段和。

第一步：计算每个数字的重量

题目内容

一个大于 $1$ 的正整数 $x$ 的重量定义为：将其分解质因数之后得到的最大的指数。例如，$90= 2^1×3^2×5^1$ ，它的重量为 $max${$1,2,1$}$=2$ 。

现在，给定 $n$ 个整数 $a_1,a_2,…,a_n$ ，小歪想找到这样不超过 $k$ 个连续的位置，满足：它们上面数字的重量之和是最大的。你只需要输出这个最大的重量之和即可。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦ T ≦ 2 × 10^5)$ 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 $n,k(1 ≦k≦n≦2× 10^5)$ ，代表整数序列的长度、最多选择连续整数的个数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(2 ≦ a_i≦ 10^7)$ ，代表整数序列。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2 × 10^5$ 。

输出描述

对于每组测试数据，新起一行。输出一个整数，代表最大的重量之和。

样例1

输入

3
7 3
4 6 5 8 1 3 2 9
5 5
2 2 2 2 9
2 1
6 8

输出

5
6
3

说明

对于第一组数据，各个数字的重量依次为：$2,1,1,3,1,1,2$ 。选择区间 $[3,5]$ (下标从 $1$ 开始计)即可。