Μόλις μετακομίσατε σε μια παράξενη γειτονιά. Παρατηρείτε ότι οι δρόμοι της γειτονιάς σας σχηματίζουν ένα δυαδικό δέντρο, με τα σπίτια να σχηματίζουν τα φύλλα του δέντρου. Αλλά αυτό δεν σας ενδιαφέρει πραγματικά, γιατί όλα έχουν να κάνουν με τα γλυκά κατά τη διάρκεια του Halloween! Ωστόσο, έχοντας μόλις μετακομίσει, μπορεί να καταλήξετε να χαθείτε. Δημιουργείτε λοιπόν ένα σχέδιο: ξεκινάτε από τη ρίζα της γειτονιάς σας και περπατάτατε σε κάθε σπίτι και ζητάτε γλυκά! Ωστόσο, πριν ξεκινήσετε την περιπέτειά σας, θέλετε να υπολογίσετε τον ελάχιστο αριθμό δρόμων που θα χρειαστεί να περπατήσετε και τη συνολική ποσότητα γλυκών που θα πάρετε.

Η είσοδος θα περιέχει 5 περιπτώσεις δοκιμής. Κάθε δοκιμαστική περίπτωση είναι μια γραμμή που περιέχει μία μόνο συμβολοσειρά, μήκους λιγότερο από 256 χαρακτήρες, που περιγράφει το δέντρο που σχηματίζει η γειτονιά σας. Ένα δυαδικό δέντρο μπορεί να περιγραφεί αναδρομικά ως εξής:

• Ένα φύλλο ~c~ , ~1 \leq c \leq 20~ , η ποσότητα της καραμέλας που λαμβάνεται από το σπίτι
• ( ~t~ ~t~ ) - όπου το ~t~ αντιπροσωπεύει ένα δέντρο

Για παράδειγμα, ένα δέντρο που αντιπροσωπεύεται από ( ( 1 5 ) 8 ) θα μοιάζει με:

Η έξοδος θα περιέχει 5 γραμμές η καθεμία θα αποτελείται από ένα ζεύγος ακεραίων ~R~ και ~C~. Το ~R~ είναι ο ελάχιστος αριθμός δρόμων που χρειάζεται να διασχίσετε για να πάρετε όλα τα γλυκά (ξεκινώντας από τη ρίζα (κορυφή) του δέντρου και δεν χρειάζεται να επιστρέψετε). Το ~C~ αντιπροσωπεύει τη συνολική ποσότητα γλυκών που θα συλλέξετε.

Παράδειγμα

input

((1 5) 8)
(1 3)

output

6 14
3 4