Easy Partition

题号：NC282702
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

给定一个长度为 $n$ 的序列 $a_1\dots a_n$ 和一个参数 $k$ 。

你需要将序列划分为若干个非空段，每个元素恰好在一个段中。令第 $i$ 个非空段为 $[l_i,r_i]$ ，则一种划分方案的权值为：

$\sum_{k\mid i}\sum_{j\in [l_i,r_i]} a_j$

即所有编号为 $k$ 的倍数的段中所有数之和。

求最大可能权值。

每个测试点中有多组数据。

$1\le T\le 10^5,\sum n\le 10^6,1\le k\le n,-10^9\le a_i\le 10^9$ 。

输入描述:

第一行，一个整数，表示数据组数 。

对于每组数据：

第一行，两个整数，表示 。

第二行， 个整数，表示 。

输出描述:

对于每组数据：一行，一个整数，表示答案。

示例1

输入

复制

3
5 3
1 2 3 4 5
5 5
92 28 39 69 -100
5 1
-29 -38 -94 -57 -61

输出

复制

12
0
-279