Time limit: 1000ms Memeory limit: 332768 kb


Problem:

嗯…动态规划专题,jibancanyang作为蒟蒻DP选手,实际上什么也不会,主要负责端茶送水,搓背揉腿,全靠紫名爷luoxinchen,图论选手liujc两位各种姿势优化dp的菊苣带领…..
所以他只能出个签到游戏题…
你要玩一个非常好玩到极度的游戏:
给你 n (2 <= n <= 60,000) 个球,每球上都写有互不相同的数字t ( 0 <= t < 100,000),这些球放在一个盒子里.开始你能执行一种加球操作:选择任意两个球: x 和y,然后看| x - y |在已经有的球中是否存在,如果不存在,就把|x - y|写在一个球上,把这个球加入这个盒子,这里就成功完成了一次加球操作.
你就一直加球,直到盒子中任意两个数的差,在集合中已经存在….
然后你把这个盒子蒙上黑布,你可以执行一种摸球操作:把手伸入盒子中,任意摸一个球出来,看一下数字,然后放回盒子.每次摸球操作每个球被摸到的概率都相同.你就一直执行摸球操作,直到所有的球都被你摸出来过的时候,好玩的游戏结束.
那么问题来了,从游戏开始到游戏结束,你执行操作的期望次数向下取整是多少?(比如期望操作次数是3.14159,那么答案是3)

输入:

第一行一个数字T(T <= 100),代表数据组数.
每行开头一个数字n,代表球数,然后接着n个不同的数,代表球上的数字.

输出:

输出数据编号和期望操作次数向下取整数的值,具体格式见样例.

样例:

2
2 1 4
3 1 2 3

10
5

By jibancanyang