SOLINFO.ro Runda 4 | twitch

După o zi grea la școală, Alex ajunge acasă și intră pe Twitch să se uite la streamer-ul lui preferat, xQc. Se pare că acesta dă un 1v1 pe Fortnite cu un alt streamer popular, Ninja. Acesta este foarte bun la Fortnite și ar putea să îl bată pe xQc foarte ușor. Însă norocul a dat ca xQc să câștige bătălia. Chat-ul a fost uimit. Toată lumea spama W pentru a celebra victoria. În caz că nu știați, W vine de la Win 🙀.

Este rândul ca Alex să celebreze victoria. El vrea să trimită $t$ mesaje pe chat, fiecare conținând $n$ caractere de W. Alex vrea să găsească numărul minim de apăsări de taste necesare pentru a scrie mesajul folosind doar tastatura. Iată o listă cu ce poate face el cu tastatura:

• Poate să apase tasta W. Astfel, va adăuga un caracter de W la sfârșitul mesajului lui.
• Poate să apese tasta BACKSPACE. Astfel, va șterge ultimul caracter din mesajul lui.
• Alex poate să apese tasta CTRL. Această tastă este mai specială, deoarece poată fi combinată cu exact o altă tastă dintre A, C sau V.
  • În timp ce tasta CTRL este apăsată, Alex poate să apese tasta A. Astfel, textul va fi selectat de calculator și poate fi folosit la combinația CTRL-C descrisă în continuare.
  • În timp ce tasta CTRL este apăsată, poate să apese tasta C. Astfel, textul selectat cu combinația CTRL-A va rămâne selectat și va fi plasat în clipboard. Funcționarea clipboard-ului este explicată în continuare.
  • În timp ce tasta CTRL este apăsată, Alex poate să apese tasta V. Astfel, există 2 cazuri:
    • Când mesajul conține o porțiune de text selectată, combinația CTRL-V va înlocui textul selectat cu ultimul text adăugat în clipboard. Textul se va deselecta automat.
    • Când mesajul nu conține nicio porțiune de text selectată, combinația CTRL-V va adăuga la sfârșitul mesajului ultimul text adăugat în clipboard.
• În sfârșit, Alex mai poate să apese tasta ENTER. Astfel, se va trimite mesajul scris de Alex către chat. După trimitere, caseta de text se va goli complet.

Atenție, Alex nu are voie să lase nicio tastă apăsată, înafară de tasta CTRL. Pentru mai multe explicații, vezi exemplele.

Cerință

Scopul tău este să faci un program care să afișeze, pentru fiecare număr $n$ din cele $t$ date, numărul minim de apăsări de taste necesare pentru a scrie un mesaj format doar din $n$ caractere de W. Tu îi vei trimite lui Alex acest program ca să îl poată folosi oricând are nevoie, iar el te va plăti cu 100 de lei puncte.

Date de intrare

Se citește din consolă pe prima linie un număr $t$.
Pe fiecare din următoarele $t$ linii se găsește numărul $n$.

Date de ieșire

Se afișează în consolă pe linia $i$ răspunsul pentru al $i$-lea $n$ citit.

Restricții și precizări

• $1 \leq n \leq 100\ 000$.
• $1 \leq t \leq 100$.
• Atenție! Punctajul obținut pe o submisie este suma maximelor subtask-urilor din toate submisiile trimise până atunci. Dacă la submisia 1 ați rezolvat doar subtask-ul $3$, iar la submisia 2 ați rezolvat doar subtask-urile $2$ și $4$, atunci punctajul final va fi constituit din subtask-urile $2$, $3$ și $4$.
• Singura modalitate de a selecta text este folosind combinația de taste CTRL-A.
• Fiecare test din cele $t$ începe cu un clipboard gol.
• Din motive necunoscute, Alex păstrează mereu tasta Caps Lock activată.
• Chiar dacă nu aveți o soluție eficientă, implementați-o. Limitele din subtask-uri pot părea foarte mari, dar de fapt nu prea sunt!

Subtask 1 (7 puncte)

• Alex poate scrie toate cele $t$ mesaje într-un număr minim de apăsări de taste folosind doar tastele W și ENTER.

Subtask 2 (9 puncte)

• $1 \leq n \leq 65$.
• Ăsta-i brutul!

Subtask 3 (14 puncte)

• Alex nu are nevoie de tasta BACKSPACE pentru a scrie toate cele $t$ mesaje într-un număr minim de apăsări de taste.
• $1 \leq n \leq 13\ 000$.

Subtask 4 (12 puncte)

• $1 \leq n \leq 4\ 000$.

Subtask 5 (21 puncte)

• $1 \leq n \leq 13\ 000$.

Subtask 6 (37 puncte)

• Fără restricții suplimentare.

Exemple și explicații

stdin

2
5
15

stdout

6
12

$n = 5$. Mesajul se poate scrie folosind $6$ apăsări de taste: W, W, W, W, W, ENTER.

$n = 15$. Mesajul se poate scrie folosind $12$ apăsări de taste.
Întâi, scriem același mesaj ca mai sus apăsând $5$ taste (W, W, W, W, W), apoi vom copia acest mesaj de încă două ori. Pentru asta, lăsăm apăsat CTRL în timp ce apăsăm următoarele taste: A, C, V, V, V. La final, apăsăm ENTER. $5 + 1 + 5 + 1 = 12$.
Aceasta nu este singura modalitate de a scrie mesajul în $12$ apăsări de taste.