Pracsiu Dan (dnprx) Virgil tocmai și-a propus să studieze proprietăți ale șirurilor. Astfel, el definește un K-șir ca fiind orice șir de numere naturale nenule care are proprietatea că orice subsecvență a sa de lungime K se poate partiționa în două subșiruri disjuncte, nu neapărat subsecvențe, având suma egală. De exemplu 1, 2, 1, 3 e un 3-șir, căci 1, 2, 1 poate fi partiționat în 1, 1 și 2, și 2, 1, 3 poate fi partiționat în 2, 1 și 3. Nu este 2-șir căci 1, 2 nu poate fi partiționat în două subșiruri cu sumă egală. Totodată nu este 4-șir.
Cerința
Pentru T șiruri de numere naturale nenule A, Virgil dorește să afle toate valorile K pentru care șirul A poate fi numit K-șir.
Date de intrare
Pe prima linie ale intrării standard se află numărul T. Urmează apoi T șiruri. Fiecare șir este dat prin două linii. Prima linie conține valoarea lui N. A doua linie conține elementele șirului separate prin câte un spațiu.
Date de ieșire
Afișați răspunsurile pentru fiecare șir în ordine. Pentru fiecare șir afișați câte o linie care conține mai întâi numărul de valori K pentru care șirul este K-șir și apoi, în ordine crescătoare, acele valori K pentru care șirul este K-șir.
Restricții și precizări
1 ≤ T ≤ 20- Suma valorilor oricărui șir este cuprinsă între
1și100.000. - Pentru 10 puncte,
1 ≤ N ≤ 30 - Pentru 20 puncte,
31 ≤ N ≤ 120 - Pentru 70 puncte,
121 ≤ N ≤ 1.000
Exemplu:
Intrare
2 7 7 3 5 1 3 3 5 6 1 2 3 5 8 3
Ieșire
2 4 6 2 3 6
Explicație
Primul șir, cel de lungime 7 este 4-șir și 6-șir, deoarece fiecare secvență de lungime 4, respectiv 6, conțin câte două subșiruri disjuncte cu suma egală care partiționează secvența.
Al doilea șir, cel de lungime 6 este 3-șir și 6-șir, deoarece fiecare secvență de lungime 3 și fiecare secvența de lungime 6 conțin câte două subșiruri disjuncte cu suma egală care partiționează secvența.