好吧是换行问题。。。

警告这道题不建议用海伦公式。
海伦公式中有乘法和开方运算
$ S=\sqrt{p(p-a)(p-b)(p-c)} $，要小心浮点误差。

由于是个图……所以我随机出来的数据有点……额……奇怪……

方丈与炽火焱的解法值得推荐。

置换的乘积就是在置换的基础上继续进行置换的意思。
如果读入的不是一个合法置换，那么将其认为是不变……如果没有这个会跪……（跪了半天然后为了调试加上了这一句……然后就过了……）

太甩节操了，上输入输出优化才过。。不过没有上非递归优化快速幂，递归效率差的很多么？

120岁的老爷爷坑了我两遍。。。习惯性for(i=0;i<101;i++)

回复 @Chenyao :
就是说，当玩的次数趋近于无穷的时候，你一直没达到目标的概率趋近于零

回复 @cstdio :
咦，好像是呀，分母无很大的时候分子也可能和”标准“差很大，是不是可以这样理解

回复 @Chenyao :
无穷次的确可以啊……

"宣布自己保持了获胜比例大于p*100%。我打败了数学规律"数学神犇，我想问个问题，如果一个人可以一天玩无数次，直到大于p*100%才停止，是不是真的可以说获胜比例大于p*100%，似乎是不是没有什么不妥啊。。。

这个。。。我发现好多题目都会附上张神奇的图片

奇偶判断少不了。
这道题输入数据比较大，所以评测机可能会有些慢，请耐心等待。

分成3种情况讨论。x轴方向，y轴方向，对角线的方向。(使n<m)
$num(x)=n*(n-1)*m;$
$num(y)=m*(m-1)*n;$
$num(x+-y=0)$
$=2*n*(m-n+1)*(n-1)+\sum_{i=1}^{n} {i(i-1)} $
$= \sum_{i=1}^{n} {i^2}-\sum_{i=1}^{n} {i} + 2*n*(m-n+1)*(n-1) $
$\sum_{i=1}^{n} {i^2}=\frac{(n+1)(2n+1)n}{6}$
$\sum_{i=1}^{n} {i}=\frac{n(n+1)}{2}$
最终化简得
$num(x+-y=0)=$
$2*n*(m-n+1)*(n-1)+\frac{(n+1)(2n+4)n}{3} $
Ans=num(x)+num(y)+num(x+-y=0)
警告PS:输入输出真心只有1组数据，且没有字符串。

开挂技能可不是印度人民独有的，图上的可是孟加拉国，蛤蛤
“But the system of the country is not that good.”真的是定体问的意思么……
这算是几何概型的一个示范

回复 @weizj :
高大上的解法……
由于T小，因此这道题在线回答更好，这个想法不错

回复 @cstdio :
好吧。。我打错了。。应该就是预处理复杂接近NLOGN的。。

回复 @cstdio :
我指的是预处理的复杂度是N*LOGN，每次询问时枚举因数再分块优化可以做到每次询问的复杂度为N^0.5（这里需要用欧拉函数预处理1到N范围内互质数对的个数），总复杂度为N*LOGN+T*N^0.5.

一定要注意输出 n(Case #n:)