### 问题描述 你有一台拥有 $n$ 个缓存页面空间的服务器，有 $k$ 个用户在同时使用。你预知了这 $k$ 个用户将会一共给出 $m$ 条页面请求。每条请求以 $x, y$ 的形式表示，表示编号为 $x$ 的用户请求了页面 $y$。这里不同用户的相同编号页面认为是不同的。你需要在开始给每个用户分配一个固定的缓存页面空间大小 $ps_i$，满足 $\sum_{i=1}^{k}{ps_i} = n$，并且使用 OPT 页面置换算法，使得总的缺页中断次数最小。 OPT 算法的具体描述为：每次当需要访问一个页面的时候，假设当前用户持有 $n_i$ 个缓存空间，首先查询该页面是否存在 $n_i$ 个缓存页面空间中，若在，则结束；若不存在，则将该页面置入 $n_i$ 个位置的其中一个（若 $n_i=0$则不操作），并触发一次缺页中断。 置入位置的选择规则如下：如果当前空间中有空的位置（为初始状态，历史未在这个位置插入过任何页面），则选择任意一个空位置插入；否则选择当前在缓存中并且**未来最久**才会被访问到的页面（未来不被再访问的认为无穷久，所如果有多个，任选一个），在该页面的位置插入新页面。一个用户的初始缓存页面空间的每个位置均处在初始状态。 ### 输入格式 本题包含多组数据。 第一行一个整数 $T$，表示数据组数。 对于每一组数据： 第一行三个整数，$n,k,m$，表示缓存页面空间，用户数，页面请求条数。 接下来 $m$ 行，每行两个整数 $x, y$ 表示一个请求。其中 $1 \leq x \leq k$。 ### 输出格式 $T$ 行，对应 $T$ 组数据的答案，每一行一个整数，表示最小缺页次数。 ### 样例输入 ```text 1 2 2 4 1 1 1 2 1 3 1 1 ``` ### 样例输出 ```text 3 ``` ### 说明 可以证明分配给第一个用户 $2$ 的空间，第二个用户 $0$ 的空间是最优的方案之一，在第 $1,2,3$ 次请求发生了缺页中断。 如果只给第一个用户分配 $1$ 的空间，则页面 $2$ 插入的时候根据规则会占用原本页面 $1$ 所占用的缓存空间，使得最后一次访问页面 $1$ 也发生缺页，总缺页中断次数为 $4$。 ### 评测数据规模 对于 $30$% 的评测数据，$0 < n, k \leq 10$。 对于 $100$% 的评测数据，$0 < T \leq 3, 0 < n, k, m \leq 1000, 0 < y \leq 10^9$。