Division Sorting Codechef Solution

Problem

Chef has an array $A$ of length $N$ consisting of positive integers.

In one move, Chef can do the following:

• Pick an index $i(1\le i\le N)$ and a prime number $P$, such that $P$ divides A_iAi​.
• Divide A_iAi​ by $P$, i.e, set A_i := \frac{A_i}{P}Ai​:=PAi​​.

Find the minimum number of moves that Chef needs to make the array $A$ non-decreasing.

Note: An array $A$ is called non-decreasing if A_i \le A_{(i+1)}Ai​≤A(i+1)​ for all $(1\le i<N)$.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of two lines of input.
  • The first line of each test case contains an integer $N$, the length of array $A$.
  • The second line contains $N$ space-separated integers A_1, A_2, \ldots, A_NA1​,A2​,…,AN​.

Output Format

• For each test case, output on a new line the minimum number of moves needed to make $A$ non-decreasing.

Constraints

Sample 1:

4
3
3 2 1
5
10 27 15 30 2
4
10 10 11 14
6
10 9 5 6 7 8

2
9
0
2

Explanation:

Test case $1$: Chef can perform the following moves:

• Divide A_1 = 3A1​=3 by $P=3$. Now, $A=[1,2,1]$
• Divide A_2 = 2A2​=2 by $P=2$. Now, $A=[1,1,1]$ and is non-decreasing.

Test case $2$: One optimal final array is $A=[1,1,1,2,2]$. You can verify that it takes $9$ moves to reach this:

• $2$ moves each on positions $1,3,$ and $4$.
• $3$ moves on position $2$.

Test case $3$: No moves need to be made. The array is already non-decreasing.

Test case $4$: Chef can divide A_1A1​ by $5$ and A_2A2​ by $3$. The array is now $[2,3,5,6,7,8]$, which is non-decreasing.