3090: 页面置换

wwh和yd最近在学习操作系统，他们对页面置换算法很感兴趣。

在操作系统中进行内存管理时，会使用页式存储管理的方法，这种方法下会将内存分成多个大小相同的块，称为物理块。每个作业的地址空间也划分成与物理块一样大小的块，称为页面。当需要某个页面时，会把这个页面调入内存中，并为其分配物理块去存储。由于内存空间有限，所以常常需要页面置换算法对页面分配进行管理。当调入一个页面时，如果这个页面未分配物理块，就根据页面置换算法把物理块中的一个页面置换成当前要访问的页面。其中页面置换算法有许多种，wwh和yd正在学习了其中两个算法：FIFO和LRU页面置换算法。

FIFO页面置换算法, 也就是先进先出的意思。即当所访问页面不在内存物理块中时，就把物理块中最先进来的页面置换为当前要访问的页面。例如如果内存空间大小是三个物理块时, 已经存了3个页面P1, P2, P3。当P4要进入内存时, 操作系统将会把P1清除, 将P4加入至内存中。如果再有P5要进入内存时, 操作系统会将P2清除，加入P5, 以此类推。

LRU页面置换算法，即最近最少使用。即当所访问页面不在内存物理块中时，就把物理块中距其上次被访问时间最久的的页面置换为当前要访问的页面。同样如果缓存空间大小是三个物理块时, 已经存了3个页面P1, P2, P3。第4次访问P1时，物理块中存有P1,即一次命中。第5次访问P4时，按照LRU算法要更换P2,因为距离它上次访问时间是最久的。

现在wwh给yd出了一道题：模拟FIFO和LRU这两个置换算法的过程。对于所给的页面访问顺序，模拟两个置换算法，分别计算到两个置换算法的命中率。当所访问的页面在物理块中时即为一次命中，命中率 = 命中次数 / 总访问次数。 将命中率以 A/B的形式表示，其中A/B为最简形式。但是yd不会计算，所以他请你来帮忙，希望你能帮助他算出结果。

第一行输入一个整数$T(T \le 60)$ ，表示测试用例的数量。

每个测试用例，第一行输入两个整数$n(1 \le n \le 1000)$和 $k(1 \le k \le 5)$分别表示访问页面个数和物理块个数，第二行输入$n$个数$a_{i}(0 \le a_{i} \le 100)$，表示页面的访问顺序。

对每组页面访问, 分别输出 FIFO 和 LRU页面置换算法的命中率 。以A/B 的形式输出，其中A/B为最简形式，如果命中率为$0$，输出$0$即可。

2
5 3
1 2 3 1 4
4 1
1 2 3 4

1/5 1/5
0 0