29717번 - 슬라임 잡고 레벨 업!

문제

오늘은 많은 사람이 기대하던 《실브 스토리》게임이 출시되는 날이다!

《실브 스토리》는 MMORPG 장르 게임으로, 몬스터를 잡아 경험치를 모으고 레벨 업을 할 수 있으며, 레벨 업에 필요한 경험치를 넘을 때마다 그에 필요한 경험치만 소진하고 남은 경험치를 그대로 보유한다. 하지만 일반 게임들과 다르게 특이한 점이 두 가지 있다.

첫 번째는 게임에 존재하는 몬스터가 슬라임뿐이라는 것이다. 슬라임을 처치했을 때 주는 경험치 또한 특이한데, 유저가 지금까지 처치한 슬라임 수를 $x$라 할 때, 새로운 슬라임을 처치하면 $x + 1$ 만큼의 경험치를 얻게 된다.

두 번째는 레벨 업에 필요한 경험치의 증가 방식이다. 현재 레벨에서 레벨 업에 필요한 경험치가 $y$라 하면 레벨 업 시 경험치 $y$를 소모한 뒤 다음 레벨 업에 필요한 경험치는 $y + 2$가 된다. 레벨 1ドル$일 경우 레벨 업 필요한 경험치는 2ドル$이다.

《실브 스토리》에 처음 접속하는 신규 유저는 레벨 1ドル,ドル 경험치 0ドル$으로 시작한다. 당연히 처치한 슬라임의 수도 0ドル$이다.

신규 유저 브실이는 지금부터 슬라임을 $N$마리 처치할 경우 자신이 레벨 몇이 될지 궁금해졌다. 슬라임을 잡을 계획을 철저하게 세우느라 바쁜 브실이를 위해 우리가 대신 브실이의 레벨이 몇이 될지 계산해 주자!

입력

첫 번째 줄에 테스트 케이스의 수 $T$가 주어진다. $(1 \le T \le 1000)$

두 번째 줄부터 $T + 1$번째 줄까지, 줄마다 정수 $N$이 주어진다. $(1 \le N \le 10^9)$

출력

각 테스트 케이스마다, 슬라임을 $N$마리 처치 후 브실이의 레벨이 얼마나 될지를 한 줄에 하나씩 출력한다.

제한

힌트