MEX-P

Problem Statement

MEX-P Problem Description You are given an array A containing N integers. Define the MEX-P of an array B as: the smallest prime that does not divide every element of B. For example, let B = [2, 4, 8] . Then MEX-P(B) = 3 , because 3 does not divide 2, while 2 - the only smaller prime - divides every element of B. Calculate the sum of MEX-P over all possible subarrays of A. A subarray is A[L..R] = [A_L, A_(L+1), ..., A_R] with 1 <= L <= R <= N . There are N * (N + 1) / 2 of them, and single-element subarrays count. Input Format The first line contains a single integer T, the number of test cases. For each test case: - The first line contains a single integer N. - The second line contains N space-separated integers, the array A. Output Format For each test case, print one line containing the sum of MEX-P over all subarrays of that test case's array. Constraints 1 <= T <= 100 1 <= N <= 15000 1 <= A_i <= 1000000000 The sum of N over all test cases does not exceed