Masala C

Sizga 1xN o‘lchamdagi setka berilgan. Boshlang‘ich holatda barcha kataklar oq rangda. Har soniyada quyidagilar sodir bo‘ladi:

1. Har bir qora rangdagi katakka qo‘shni bo‘lgan kataklar qora rangga bo‘yaladi. Har bir qora rangdagi $x$-katak uchun $x+1$-inchi va $x-1$-inchi kataklar ham (agar mavjud bo‘lsa) qora rangga bo‘yaladi.
2. Xohlagan bir katakni qora rangga bo‘yashingiz mumkin.

Savol:

Barcha kataklarni qora rangga bo‘yash uchun eng kamida qancha vaqt kerak bo‘ladi?

Birinchi qatorda T soni $(1\le T \le 100)$ - Testlar soni.

Keyingi T qatorda N soni $(1 \le N \le 10^9)$.

To'ldirish uchun eng kam vaqt(sekund) ketishini chop eting.