【题意】

小象喜欢为箱子涂色。

小象现在有c种颜色，编号为0~c-1；

还有n个箱子，编号为1~n，最开始每个箱子的颜色为1。

小象涂色时喜欢遵循灵感：它将箱子按编号排成一排，每次涂色时，它随机选择[L，R]这个区间里的一些箱子，为之涂上随机一种颜色。

若一个颜色为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