EXPOR - OR


Given an array of N integers A1, A2, A3…AN. If you randomly choose two indexes i ,j such that 1 ≤ i < j ≤ N, what is the expected value of Ai | Aj?

Input

First line contains an integer T, the number of test cases. Each test case consists of two lines. First line denotes the size of array, N and second line contains N integers forming the array.
1 ≤ T ≤ 10
2 ≤ N ≤ 100,000
0 ≤ Ai < 231

Output

For each test case, print the answer as an irreducible fraction. Follow the format of the sample output.
The fraction p/q (p and q are integers, and both p ≥ 0 and q > 0 holds) is called irreducible, if there is no such integer d > 1 that divides both p and q separately.

Example

Input:
2
2
0 0
3
1 2 3

Output:
0/1
3/1

hide comments
geeta: 2017-05-25 15:29:05

What is the expected time complexity? My algo is running in O(31*N) and getting TLE. How to optimise it further?

eightnoteight: 2016-10-29 23:07:44

OMG!!!!!!!
I had to do super crazy things to get AC in Java instead of TLE and WA

any tips from other java programmers to further optimize it????

Last edit: 2016-10-29 23:09:31
smtcoder: 2016-09-09 23:47:08

After 3 TLEs and 1 WA..Got accepted...
Highly recommended question..Concept used in it is amazing..!!
But Reason why there are so many submissions of this question only 10% of them accepted is because of just one thing which u must find yourself..it will be fun..!! :D

Last edit: 2016-09-09 23:47:28
sumitsinghnit: 2016-09-08 13:58:14

Required a lot of optimizations to get AC.

Last edit: 2017-05-11 07:30:02
rayhan50001: 2016-09-06 01:23:43

"f there is no such integer dā€‰>ā€‰1 that divides both p and q separately."
what do you mean by that???

:D: 2016-08-29 21:44:23

bitwise or

slaski: 2016-08-29 16:44:28

Would be good to define `a | b`. Isn't it binary or?

:D: 2016-08-29 11:11:27

For the first test case only pair is (0 0) so the result is 0|0 = 0. For second case we have 3 pairs (1 2) (1 3) (2 3). Or values are 1|2 = 3, 1|3 = 3, 2|3 = 3. So the average is 3.

Vipul Srivastava: 2016-08-28 19:10:34

Please explain a test case if possible..


Added by:Evan
Date:2016-08-26
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:https://algo.codemarshal.org/contests/goc-0101