마그누스라는 영웅

Dota 2는 Valve가 개발하고 배급하는 멀티플레이어 온라인 전투 아레나(MOBA) 비디오 게임이다. Dota 2 경기는 다섯 명씩 이루어진 두 팀이 맵에서 각자 분리된 기지를 차지하고 방어하며 치른다. 열 명의 플레이어는 각자 독립적으로 '영웅'이라 불리는 강력한 캐릭터를 조종한다. 영웅마다 고유한 능력과 서로 다른 플레이 방식이 있다. 경기 중 플레이어는 경험치와 아이템을 모아 영웅을 성장시키고, 이 영웅으로 플레이어 간 전투에서 상대 팀 영웅을 쓰러뜨린다. 상대 팀 기지 안에 있는 거대한 건축물 'Ancient'를 먼저 파괴하는 팀이 승리한다.

The International은 Valve가 개최하고 제작하는 Dota 2 연례 e스포츠 세계 선수권 대회다. 대회에는 18개 팀이 참가한다. 12개 팀은 Dota Pro Circuit의 최종 성적으로 선발되고, 나머지 6개 팀은 북미, 남미, 동남아시아, 중국, 동유럽, 서유럽 지역 예선에서 우승한 팀이다.

3021년, The International은 중국 구이린에서 열린다. 1000년 전과 마찬가지로 중국의 LGD가 러시아의 Team Spirit과 맞붙는다. 대회 규칙은 n판 중 먼저 $\frac{n+1}{2}$승을 거두는 팀이 우승하는 방식이며, 여기서 $n$은 양의 홀수다. 2021년에는 $n$이 $5$였고 Team Spirit이 $3:2$로 이겼다.

경기 시작 전 팀들은 상대 팀이 특정 영웅을 쓰지 못하도록 밴(금지)할 수 있다. 이 1000년 동안 모두가 Team Spirit이 마그누스(Magnus)를 아주 잘 쓴다는 것을 알고 있다. 2021년에도 이 마그누스 덕분에 Team Spirit이 LGD를 꺾었다.

모두가 LGD가 처음부터 마그누스를 밴할 것이라고 생각하지만, LGD의 생각은 다르다. 그들은 상대의 마그누스를 이길 만큼 충분히 강하다고 여기며, $x$번째 경기가 있는 경우에만 $x$번째 경기부터 마그누스를 밴하기 시작한다.

간단히 말해, LGD가 마그누스를 밴하면 그 경기는 반드시 이긴다. 그렇지 않으면 그 경기를 $50\%$의 확률로 이길 수 있다.

LGD의 팬인 JB는 최악의 경우에도 LGD가 우승할 수 있는 최소의 $n$을 알고 싶어 한다.

첫 줄에 정수 $T$($1 \leq T \leq 10^5$)가 주어진다. 테스트 케이스의 수다.

이어서 $T$개의 줄에 각각 정수 $x$($1 \leq x \leq 2 \times 10^9$)가 주어진다. 이는 LGD가 $x$번째 경기부터 마그누스를 밴하기 시작한다는 뜻이다.

각 테스트 케이스마다 LGD가 우승하는 데 필요한 경기 수 합계의 최솟값을 한 줄에 출력한다.

모두의 가장 강한 바람을 무시하면, 테스트 데이터에 $x>1$인 경우가 있다. 이는 LGD가 항상 처음부터 마그누스를 밴하지는 않는다는 뜻이다.