YAPTCHA

선영이는 문제를 풀 때마다 자신의 Practice Log에 풀이법을 올려놓는다. 이 사이트는 매우 유명해져서 하루에 백만 명이 방문하는 사이트가 되었다.

선영이는 풀이를 읽지 않고 소스 코드만 복사해 온라인 저지에 제출하는 사람들을 싫어한다. 이를 막기 위해 홈페이지에 Yet-Another-Public-Turing-test-to-tell-Computers-and-Humans-Apart(YAPTCHA)를 추가하기로 했다.

이 YAPTCHA 테스트는 매우 어려워서 박사 학위를 받은 학생이나 교수도 쉽게 풀지 못한다. 풀이를 보고 싶은 상근이는 이 테스트를 자동으로 푸는 프로그램을 만들려고 한다.

홈페이지에 접속하면 자연수 $n$과 함께 다음 식이 주어진다. 이 식의 값 $S_n$을 계산해 입력하면 풀이를 볼 수 있다. $n$이 주어졌을 때 $S_n$을 구하는 프로그램을 작성하시오.

여기서 $\lfloor x \rfloor$는 $x$보다 크지 않은 가장 큰 정수(바닥 함수)를 의미한다.

첫째 줄에 쿼리의 수 $t$ ($t \le 10^6$)가 주어진다. 이어서 각 쿼리가 한 줄에 하나씩 주어지며, 각 쿼리는 자연수 $n$ ($1 \le n \le 10^6$) 하나로 이루어져 있다.

각 쿼리로 주어진 $n$에 대해 $S_n$을 한 줄에 하나씩 출력한다.