지난 놀이도 따분해진 선용이는, 고민 끝에 오랫동안 즐길 수 있는 게임을 구상했다. 구체적으로 다음과 같다.

1. $1, 2, ... , n$의 번호가 매겨진 $n$개의 정점을 새롭게 그려 놓는다.
2. 다음을 만족하는 정점 $i, j$를 고른다. $(1 ≤ i, j ≤ n; i ≠ j)$
• 지금까지 정점 $i$에서 나가는 간선은 존재하지 않았다.
• 지금까지 정점 $j$로 들어오는 간선은 존재하지 않았다.
3. 조건에 맞는 정점 $i, j$를 골랐다면 $i$에서 $j$로 향하는 간선을 추가하고 $2$로 돌아간다.
4. 조건에 맞는 정점 $i, j$를 고르지 못했다면 다음을 따른다.
• $n$개의 간선을 추가했고, 완성된 그래프가 지금까지 한 번도 만들어지지 않은 그래프라면 $1$점을 획득한다.
• 더 이상 새로운 형태의 그래프가 만들어질 수 없다면 놀이를 종료한다.
• 새로운 형태의 그래프가 아직 만들어질 가능성이 있다면 $1$로 돌아간다.

선용이는 $n$이 작을 땐 얻을 수 있는 최대 점수를 쉽게 알아냈지만, $n$이 커질수록 얻을 수 있는 최대 점수를 알아내는 데에 어려움을 느꼈다.

선용이를 위해 $n$이 주어졌을 때 얻을 수 있는 최대 점수를 알려주는 프로그램을 작성해주도록 하자!

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

둘째 줄부터 $T$개의 줄에 걸쳐 정점의 개수 $n$이 주어진다. $(1 ≤ n ≤ 10^6)$

1. $n = 1$
• $n$개의 간선을 추가하지 못했고 더 이상 새로운 그래프가 만들어질 가능성이 없으므로 놀이를 종료한다.
2. $n = 2$
• $1 → 2$, $2 → 1$로 간선을 추가해 $1$점을 획득하고 난 후, 더 이상 새로운 그래프가 만들어질 가능성이 없으므로 놀이를 종료한다.
  
3. $n = 3$
• $1 → 2$, $2 → 3$, $3 → 1$로 간선을 추가해 $1$점을 획득한다.
  
• $1 → 3$, $3 → 2$, $2 → 1$로 간선을 추가해 $1$점을 획득한다.
  
• 더 이상 새로운 그래프가 만들어질 가능성이 없으므로 놀이를 종료한다.