题目内容

小塔正在对一个长度为n的数组a进行染色。初始时所有元素均为无色。他每次可以选择以下操作之一：

• 选择一个索引将其染成红色。

• 选择一个区间[$l,r$]，如果该区间内红色元素的个数多于无色元素的个数，则将这个区间内的所有元素全部染成红色。

  小塔至少需要多少次操作，才能将整个数组全部染成红色？

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T$($1≤T≤10^5$)代表数据组数，每组测试数据描述如下: 在一行上输入一个整数$n$($1≤n≤10^9$)代表数组中的元素数量。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表将整个数组全部染成红色所需的最少操作次数。

样例1

输入

3
3
4
12

输出

3
4
6