Mod Equality solution codechef

Mod Equality solution codechef

You are given NN non-negative integers A1,A2,,ANA1,A2,…,AN. You are allowed to perform following operation any number of times:

• Choose any valid index ii (1iN1≤i≤N) and a positive integer M>0M>0 and replace AiAi with AimodMAimodM. That is, replace AiAi with its remainder when divided by MM, which is a value between 00 and M1M−1, inclusive.
• MM does not need to be same between different operations.

Find the minimum number of operations to make all the array elements equal.

Note: Since the input and output are large, prefer using fast input-output methods.

Input Format

• The first line contains an integer TT – the number of test cases. Then TT test cases follow.
• The first line of each test case contains an integer NN – the size of array.
• The second line contains NN integers A1,A2,,ANA1,A2,…,AN – the elements of the array.

Output Format

For each test, print one line containing an integer which denotes minimum number of operations performed to make all the elements equal.

Constraints

• 1T1041≤T≤104
• 1N1051≤N≤105
• 0Ai21090≤Ai≤2⋅109
• It is guaranteed that the sum of NN over all test cases does not exceed 106106.

2
3
2 1 3
3
1 1 3

3
1

Explanation

In first test case, we can make all the elements equal by following operations:

• Take i=1i=1 and M=2M=2 and do A1:=A1mod2=0A1:=A1mod2=0.
• Take i=2i=2 and M=1M=1 and do A2:=A2mod1=0A2:=A2mod1=0.
• Take i=3i=3 and M=3M=3 and do A3:=A3mod3=0A3:=A3mod3=0.
After these 33 operations we have all the elements equal to zero.

In second test case, we can perform following operation:

• Choose i=3i=3 and M=2M=2 and do A3:=A3mod2=1A3:=A3mod2=1.
After this operation all the elements are 11.