Prüfer Code I

The Prüfer code is a very compact way to represent a labeled tree.

We can represent a tree as a string with the following rules: (Pseudo BNF)

tree = node | node '(' tree [ ',' tree ] ')' 
node = an integer

For examples:

---

1(2(3(4,5)))

---

1(2(3),4,5)

---

Consider a labeled tree with n nodes labeled $1,2,\dots ,n$ in sequential order.

We can see its Prüfer code as the base 10 representation of some integer.

For instance, the tree $1(2(3,4(5)),6(7),8)$ has the following Prüfer code $\{2,4,2,1,6,1\}$ = $242161$

Find all labeled trees with 10 nodes whose Prüfer code correspond to a prime number.
Among these trees find those whose Prüfer code contain distinct values.

Answer format: Sum of the values , (/ delimited list of the trees in string representation - lexicographic order)

Example: 11006162,1(2(3(4(5(6)))),7(8))/1(2(3(4(5))),6(7(8))) // For 8 nodes

[My timing: instant]