题目描述：

小象喜欢为箱子涂色。小象现在有c种颜色，编号为0~c-1；还有n个箱子，编号为1~n，最开始每个箱子的颜色为1。小象涂色时喜欢遵循灵感：它将箱子按编号排成一排，每次涂色时，它随机选择[L，R]这个区间里的一些箱子（不选看做选0个），为之涂上随机一种颜色。若一个颜色为a的箱子被涂上b色，那么这个箱子的颜色会变成（a*b）mod c。请问在k次涂色后，所有箱子颜色的编号和期望为多少？

输入描述：

第一行为T，表示有T组测试数据。
对于每组数据，第一行为三个整数n,c,k。
接下来k行，每行两个整数Li，Ri，表示第i个操作的L和R。

输出描述：

对于每组测试数据，输出所有箱子颜色编号和的期望值，结果保留9位小数。

样例输入：

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

样例输出：

2.062500000
1.000000000
3.875000000

数据范围：

40%的数据1 <= T <= 5，1 <= n, k <= 15，2 <= c <= 20
100%的数据满足1 <= T <= 10，1 <= n, k <= 50，2 <= c <= 100，1 <= Li <= Ri <= n