409890: GYM103828 C Basharo is not ugly

let's define some concepts:

• Let $$$\textbf{ugliness}(x)$$$ be the number of distinct prime factors of integer $$$x$$$.
• The ugliness of an array $$$a$$$ is the sum of the ugliness of its elements.

• The cost of an array $$$a$$$ is equal to the sum of its elements.

Now, you are given an integer array $$$a$$$ and two integers $$$l,r\space (l\le r)$$$ and you are asked to distribute the elements of this array between two arrays $$$b$$$ and $$$c$$$ where each element $$$a_i$$$ must belong to exactly one of the arrays $$$b$$$ or $$$c$$$.

A distribution is called valid if the ugliness of $$$b$$$ is between $$$l$$$ and $$$r$$$.

Among all the valid distributions of $$$a$$$, you must find the one that minimizes $$$ |cost(b) - cost(c)| $$$.

Print the minimum value of $$$ |cost(b) - cost(c)| $$$ you can get or print $$$-1$$$ if there's no valid distribution.

The first line of the input contains a single integer $$$T$$$, ($$$1 \le T \le 20$$$), the number of test cases.

Each test case consists of two lines. The first line contains three space-separated integers $$$n, l, r$$$ ($$$1\le n\le 100$$$), ($$$1\le l\le r \le 55$$$).

The second line contains $$$n$$$ space separated integers $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_i\le 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all the test cases does not exceed $$$100$$$ and that the sum of $$$a_i$$$ over each test case does not exceed $$$10^6$$$.

For each test case, in a single line, if there's no valid distribution print $$$-1$$$ otherwise print the minimum possible value of $$$ |cost(b) - cost(c)|$$$.

3
6 2 4
1 1 2 2 2 2
6 1 6
1 1 1 1 1 1
6 1 6
2 2 2 2 2 2

0
-1
0

In the first test case, we distribute $$$a$$$ as follow: $$$b = 1,2,2$$$ , $$$c = 1,2,2$$$.

The ugliness of $$$b$$$ is $$$2$$$ which is satisfy $$$l\le 2\le r$$$.

The $$$cost(b) = 5, cost(c) =5$$$ so the answer is $$$|5-5|=0$$$ (the minimum possible answer).