Tramvaj

Το δίκτυο τραμ μιας συγκεκριμένης πόλης μπορεί να αναπαρασταθεί ως ~n~ σταθμοί τραμ, τοποθετημένοι σε ίσες αποστάσεις πάνω σε έναν κύκλο. Οι σταθμοί του τραμ αριθμούνται με θετικούς ακέραιους από το ~1~ έως το ~n~, κατά τη φορά των δεικτών του ρολογιού. Υπάρχει ακριβώς μία γραμμή μεταξύ κάθε δύο σταθμών και τα τραμ κινούνται πάντα δεξιόστροφα.

Μια διαδρομή μήκους ~l~ (~1 \le l \le n - 1~) σας μεταφέρει από τον τρέχοντα σταθμό σας στον σταθμό που βρίσκεται ~l~ στάσεις πιο πέρα, προς τη δεξιόστροφη κατεύθυνση.

Η Διοίκηση του Τραμ πουλάει ξεχωριστό εισιτήριο για κάθε μήκος διαδρομής. Στο πλαίσιο μιας διαφημιστικής καμπάνιας, αποφάσισε να χρωματίσει κάθε τύπο εισιτηρίου και να προσφέρει μια δωρεάν μηνιαία κάρτα απεριορίστων διαδρομών σε οποιοδήποτε άτομο που:

• επιστρέφει, μέσω μιας ακολουθίας διαδρομών, στον σταθμό από τον οποίο ξεκίνησε, και
• χρησιμοποιεί εισιτήρια με χρώματα ανά δύο διαφορετικά σε αυτό το ταξίδι.

Τα στελέχη της Διοίκησης ενθουσιάστηκαν με την ιδέα του χρωματισμού των εισιτηρίων ως διαφημιστική στρατηγική, αλλά όχι με την ιδέα να χρησιμοποιεί κάποιος τα τραμ τους δωρεάν. Έτσι, θα συμφωνήσουν με τον χρωματισμό μόνο αν κανένα άτομο δεν μπορεί να κερδίσει τη δωρεάν μηνιαία κάρτα.

Φυσικά, όλα τα εισιτήρια θα μπορούσαν να έχουν το ίδιο χρώμα, αλλά τότε θα ήταν αμέσως προφανές στο κοινό ότι είναι αδύνατο να κερδίσει τη δωρεάν μηνιαία κάρτα. Χωρίς να ανησυχούν για τις συνέπειες μιας παραπλανητικής διαφήμισης, τα στελέχη σάς ζητούν να βρείτε έναν χρωματισμό που χρησιμοποιεί όσο το δυνατόν περισσότερα διαφορετικά χρώματα!

Είσοδος

Η πρώτη γραμμή θα περιέχει έναν θετικό ακέραιο ~t~ (~1 \le t \le 1000~), τον αριθμό των σεναρίων.

Καθεμία από τις επόμενες ~t~ γραμμές θα περιέχει έναν θετικό ακέραιο ~n~ (~2 \le n \le 2 \cdot 10^5~), τον αριθμό των σταθμών του δικτύου.

Το άθροισμα των τιμών του ~n~ σε όλα τα σενάρια δεν θα υπερβαίνει το ~2 \cdot 10^5~.

Έξοδος

Για καθένα από τα ~t~ σενάρια, με τη σειρά που δίνονται, να εκτυπώσετε δύο γραμμές.

Στην πρώτη γραμμή, να εκτυπώσετε έναν θετικό ακέραιο ~k~, τον αριθμό των χρωμάτων που χρησιμοποιούνται για τον χρωματισμό των εισιτηρίων.

Στη δεύτερη γραμμή, να εκτυπώσετε ~n - 1~ αριθμούς ~c_1, ..., c_{n-1}~, διαχωρισμένους με κενά, όπου ο ~c_i~ είναι το χρώμα του εισιτηρίου για διαδρομή μήκους ~i~. Κάθε χρώμα πρέπει να είναι ένας θετικός ακέραιος από το σύνολο ~\{1, 2, ..., k\}~, και κάθε αριθμός αυτού του συνόλου πρέπει να εμφανίζεται τουλάχιστον μία φορά.

Βαθμολογία

Σε κάθε σενάριο, έστω ~k~ ο αριθμός των χρωμάτων που εκτυπώνει η λύση σας και ~k_{opt}~ ο μέγιστος δυνατός αριθμός χρωμάτων.

Αν ο χρωματισμός που εκτυπώνεται σε οποιοδήποτε σενάριο δεν ικανοποιεί τις προϋποθέσεις του προβλήματος, η λύση λαμβάνει ~0~ βαθμούς σε εκείνο το αρχείο ελέγχου.

Διαφορετικά, για κάθε σενάριο υπολογίζουμε τον λόγο:

~r = \begin{cases} 1, & \text{if } k_{opt} = 1 \text{ and } k = 1,\\ \dfrac{k - 1}{k_{opt} - 1}, & \text{if } k_{opt} > 1. \end{cases}~

Το ποσοστό των βαθμών που κερδίζονται σε ένα αρχείο ελέγχου είναι ο ελάχιστος λόγος ~r~ μεταξύ όλων των σεναρίων αυτού του αρχείου ελέγχου.

Οι βαθμοί που κερδίζονται σε ένα υποπρόβλημα ισούνται με τη βαθμολογική του αξία πολλαπλασιασμένη με το ελάχιστο αντίστοιχο ποσοστό μεταξύ όλων των αρχείων ελέγχου αυτού του υποπροβλήματος.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~20~	~n \le 12~
~2~	~10~	Το ~n~ είναι πρώτος αριθμός.
~3~	~15~	Το ~n~ είναι δύναμη του ~2~.
~4~	~65~	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

1
3

output

1
1 1

input

2
4
5

output

2
2 1 2
2
1 2 2 1

input

1
6

output

2
2 1 2 1 2