# Division Sorting Codechef Solution

### We Are Discuss About CODECHEF SOLUTION

Division Sorting Codechef Solution

## 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 \leq i \leq N) and a prime number P, such that P divides A_i.
• Divide A_i by P, i.e, set A_i := \frac{A_i}{P}.

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)} for all (1 \le i \lt 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_N.

### Output Format

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

### Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 2 \cdot 10^5
• 1 \leq A_i \leq 5\cdot 10^5
• The sum of N across all test cases won’t exceed 2 \cdot 10^5.

### Sample 1:

Input

Output

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 = 3 by P = 3. Now, A = [1, 2, 1]
• Divide A_2 = 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_1 by 5 and A_2 by 3. The array is now [2, 3, 5, 6, 7, 8], which is non-decreasing. ## Division Sorting Codechef Solution

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW 