# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Vishesh Saraswat

*Nishank Suresh, Satyam*

**Testers:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

1185

# PREREQUISITES:

Knowledge of GCD

# PROBLEM:

You have an array A. In one move you can choose an index i and set A_i \to \frac{A_i}{X} where X is some factor of A_i.

Find the minimum number of moves needed to make all the elements equal.

# EXPLANATION:

Suppose we make some moves and end up with all the elements equal, say to an integer y.

Then, notice that y must divide *every* A_i, since one operation only allows us to replace an element with one of its factors.

Since y must divide every A_i, y must also divide \gcd(A_1, A_2, \ldots, A_N).

Now notice that we might as well choose y = \gcd(A_1, A_2, \ldots, A_N), because:

- It obviously satisfies the condition that it divides every element of A
- It is the largest possible integer that satisfies this condition

This gives a rather simple solution:

- Compute y = \gcd(A_1, \ldots, A_N).
- To do this, first initialize y = A_1. Then, for each i \gt 1, set y = \gcd(y, A_i).
- Computing the gcd of two elements can be done using inbuilt functions, like
`std::gcd`

in C++ and`math.gcd`

in Python.

- Then, for each A_i:
- If A_i = y, we don’t need to change this element at all.
- Otherwise, we need exactly one move to turn A_i into y.

So, count the number of times y appears in the array — let this be k. The answer is then N - k.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

## Editorialist's code (Python)

```
from math import gcd
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
g = a[0]
for x in a:
g = gcd(x, g)
print(n - a.count(g))
```