Cute Chef Gift SOLUTION
Chef wants to give a gift to Chefina to celebrate their anniversary. Of course, he has a sequence a1,a2,…,aN ready for this occasion. Since the half-heart necklace is kind of cliche, he decided to cut his sequence into two pieces and give her a piece instead. Formally, he wants to choose an integer l (1≤l<N) and split the sequence into its prefix with length l and its suffix with length N−l.
Chef wants his gift to be cute; he thinks that it will be cute if the product of the elements in Chefina’s piece is coprime with the product of the elements in his piece. Can you tell him where to cut the sequence? Find the smallest valid l such that Chef’s gift would be cute.
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains the integer N.
The second line contains N space-separated integers a1,a2,…,aN.
For each test case, print a single line containing one integer l where Chef should cut the sequence.
It is guaranteed that a solution exists for the given test data.
2≤ai≤105 for each valid i
the sum of N over all test cases does not exceed 3⋅105
Subtask #1 (25 points):
the sum of N over all test cases does not exceed 600
Subtask #2 (40 points):
the sum of N over all test cases does not exceed 6,000
Subtask #3 (35 points): original constraints
2 3 4 5
SOLUTION AFTER CONTEST
Free Coupon is Applied Claim the Offer!
November Challenge 2020 SOLUTION CodeChef
- Selecting Edges SOLUTION SELEDGE
- Panic! at the Disco SOLUTION PANIC
- Restore Sequence SOLUTION RESTORE
October Lunchtime 2020 CodeChef SOLUTIONS