문제

태우는 오늘도 저녁에 무엇을 먹을지 정하지 못해 고민하고 있다. 고민 끝에, 저녁 메뉴를 정하기 위해 개의 후보 메뉴를 놓고 토너먼트를 진행하기로 했다. 토너먼트는 다음 규칙에 따라 메뉴가 1개 남을 때까지 반복하여 진행한다.

• 현재 개의 메뉴가 남아있을 때, 남아있는 메뉴를 임의로 둘씩 짝지어 개의 쌍을 만든다.
• 각 쌍에 대해 경기를 치른 뒤 승리하는 메뉴가 다음 라운드에 진출한다.
• 이 홀수여서 짝을 짓지 못한 메뉴는 부전승으로 다음 라운드에 진출한다.

태우는 개의 메뉴로 토너먼트를 진행할 때 부전승이 몇 번 발생하는지 궁금해졌다. 태우를 도와 부전승이 발생하는 횟수를 구하여라.

입력

첫째 줄에 테스트 케이스의 수 가 주어진다. ()

둘째 줄부터 개의 줄에 걸쳐 각 테스트 케이스의 토너먼트의 초기 후보 수 이 한 줄에 하나씩 주어진다. ()

출력

각 테스트 케이스에 대해 토너먼트를 진행할 때 발생하는 부전승의 횟수를 한 줄에 하나씩 출력한다.