子树的大小

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

题目描述

牛牛有一颗包含 $n$ 个结点的 $k$ 叉树，这些结点编号为 $0…n-1$ 。

定义一颗 $k$ 叉树：
1、以结点 0 为根。
2、编号为 $x$ 结点的 $k$ 个儿子编号分别为： $k\times x + 1…k\times x + k$ 。

牛妹有 $m$ 个询问表示为： $q_1,q_2…q_m$ 。

对于第 $i$ 个询问，你需要告诉牛妹编号为 $q_i$ 的结点，其的子树中结点的个数（含结点 $q_i$ ）。

输入描述:

本题采用多组案例输入，第一行一个整数 $T$ 代表案例组数。
每组案例中，第一行包含三个空格分隔的整数： $n\ k\ m$ 。
接下来一行包含 $m$ 个空格分隔的整数代表： $q_1,q_2…q_m$ 。
保证：
$0 < n \le 10^{16}$
$0 < k \le 100$
$0 < m \le 10^5$
$0 \le q_i < n$

单个测试点中所有案例 $m$ 的和不超过 $3\times 10^5$

输出描述:

对于每组案例，输出共  行，每行一个整数代表答案。

示例1

输入

复制

输出

复制