시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 174 69 65 43.919%

문제

선영이는 문제를 풀 때마다 Practice Log에 문제의 풀이법을 올려놓는다. 이 사이트는 매우 유명해졌고, 하루에 백만명이 들어오는 사이트가 되었다.

선영이는 풀이를 읽지 않고 소스만 긁어서 온라인 저지에 제출하는 사람들을 정말 싫어한다. 이런한 일을 막기 위해서 Yet-Another-Public-Turing-Test-to-Tell-Computers-and-Humans-Apart를 홈페이지에 추가하기로 했다.

선영이가 만든 YAPTCHA 테스트는 매우 어려워서 박사학위를 받은 학생이나 교수도 쉽게 풀 수 없다. 문제의 풀이법을 보고싶어하는 상근이는 자동으로 테스트를 푸는 프로그램을 만드려고 한다.

선영이의 홈페이지에 들어가면 자연수 n과 다음과 같은 식이 주어진다. 식을 계산한 뒤, Sn을 입력하면 문제의 풀이를 볼 수 있다. n이 주어졌을 때, Sn을 구하는 프로그램을 작성하시오.

\[S_{n} =\sum _{ k=1 }^{ n }{ \left[ \frac{(3k+6)!+1}{3k+7}-\left[ \frac{(3k+6)!}{3k+7} \right]  \right]  }  \]

[x]는 x보다 크지 않은 가장 큰 정수를 말한다.

입력

첫째 줄에 쿼리의 수 t (t ≤ 106)가 주어진다. 각 쿼리는 자연수 n 하나로 이루어져 있다. (1 ≤ n ≤ 106)

출력

입력으로 주어진 n에 대해서 Sn을 출력한다. 

예제 입력 1

13
1
2
3
4
5
6
7
8
9
10
100
1000
10000

예제 출력 1

0
1
1
2
2
2
2
3
3
4
28
207
1609
W3sicHJvYmxlbV9pZCI6Ijc4ODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJZQVBUQ0hBIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MCBcdWI1NGNcdWI5YzhcdWIyZTQgUHJhY3RpY2UgTG9nXHVjNWQwIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWQ0ODBcdWM3NzRcdWJjOTVcdWM3NDQgXHVjNjJjXHViODI0XHViMTkzXHViMjk0XHViMmU0LiBcdWM3NzQgXHVjMGFjXHVjNzc0XHVkMmI4XHViMjk0IFx1YjllNFx1YzZiMCBcdWM3MjBcdWJhODVcdWQ1NzRcdWM4NGNcdWFjZTAsIFx1ZDU1OFx1YjhlOFx1YzVkMCBcdWJjMzFcdWI5Y2NcdWJhODVcdWM3NzQgXHViNGU0XHVjNWI0XHVjNjI0XHViMjk0IFx1YzBhY1x1Yzc3NFx1ZDJiOFx1YWMwMCZuYnNwO1x1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1ZDQ4MFx1Yzc3NFx1Yjk3YyBcdWM3N2RcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YzE4Y1x1YzJhNFx1YjljYyBcdWFlMDFcdWM1YjRcdWMxMWMgXHVjNjI4XHViNzdjXHVjNzc4IFx1YzgwMFx1YzljMFx1YzVkMCBcdWM4MWNcdWNkOWNcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQ0IFx1YzgxNVx1YjlkMCBcdWMyZWJcdWM1YjRcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjdmMFx1ZDU1YyBcdWM3N2NcdWM3NDQgXHViOWM5XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBZZXQtQW5vdGhlci1QdWJsaWMtVHVyaW5nLVRlc3QtdG8tVGVsbC1Db21wdXRlcnMtYW5kLUh1bWFucy1BcGFydFx1Yjk3YyBcdWQ2NDhcdWQzOThcdWM3NzRcdWM5YzBcdWM1ZDAgXHVjZDk0XHVhYzAwXHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YjljY1x1YjRlMCBZQVBUQ0hBIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHVjNWI0XHViODI0XHVjNmNjXHVjMTFjIFx1YmMxNVx1YzBhY1x1ZDU1OVx1YzcwNFx1Yjk3YyBcdWJjMWJcdWM3NDAgXHVkNTU5XHVjMGRkXHVjNzc0XHViMDk4Jm5ic3A7XHVhZDUwXHVjMjE4XHViM2M0IFx1YzI3ZFx1YWM4YyBcdWQ0ODAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHViYjM4XHVjODFjXHVjNzU4IFx1ZDQ4MFx1Yzc3NFx1YmM5NVx1Yzc0NCBcdWJjZjRcdWFjZTBcdWMyZjZcdWM1YjRcdWQ1NThcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc5MFx1YjNkOVx1YzczY1x1Yjg1YyBcdWQxNGNcdWMyYTRcdWQyYjhcdWI5N2MgXHVkNDc4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWM3NTggXHVkNjQ4XHVkMzk4XHVjNzc0XHVjOWMwXHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwMFx1YmE3NCBcdWM3OTBcdWM1ZjBcdWMyMTggblx1YWNmYyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzJkZFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzJkZFx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NWMgXHViNGE0LCBTPHN1Yj5uPFwvc3ViPlx1Yzc0NCBcdWM3ODVcdWI4MjVcdWQ1NThcdWJhNzQgXHViYjM4XHVjODFjXHVjNzU4IFx1ZDQ4MFx1Yzc3NFx1Yjk3YyBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBTPHN1Yj5uPFwvc3ViPlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XFxbU197bn0gPVxcc3VtIF97IGs9MSB9XnsgbiB9eyBcXGxlZnRbIFxcZnJhY3soM2srNikhKzF9ezNrKzd9LVxcbGVmdFsgXFxmcmFjeygzays2KSF9ezNrKzd9IFxccmlnaHRdICZuYnNwO1xccmlnaHRdICZuYnNwO30gJm5ic3A7XFxdPFwvcD5cclxuXHJcbjxwPlt4XVx1YjI5NCB4XHViY2Y0XHViMmU0IFx1ZDA2Y1x1YzljMCBcdWM1NGFcdWM3NDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM4MTVcdWMyMThcdWI5N2MgXHViOWQwXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNmZmNcdWI5YWNcdWM3NTggXHVjMjE4IHQgKHQgJmxlOyAxMDxzdXA+NjxcL3N1cD4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1Y2ZmY1x1YjlhY1x1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggbiBcdWQ1NThcdWIwOThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTA8c3VwPjY8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgblx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgUzxzdWI+bjxcL3N1Yj5cdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc4ODEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJZQVBUQ0hBIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgbWF0aCBkZXBhcnRtZW50IGhhcyBiZWVuIGhhdmluZyBwcm9ibGVtcyBsYXRlbHkuIER1ZSB0byBpbW1lbnNlIGFtb3VudCBvZiB1bnNvbGljaXRlZCBhdXRvbWF0ZWQgcHJvZ3JhbXMgd2hpY2ggd2VyZSBjcmF3bGluZyBhY3Jvc3MgdGhlaXIgcGFnZXMsIHRoZXkgZGVjaWRlZCB0byBwdXQgWWV0LUFub3RoZXItUHVibGljVHVyaW5nLVRlc3QtdG8tVGVsbC1Db21wdXRlcnMtYW5kLUh1bWFucy1BcGFydCBvbiB0aGVpciB3ZWJwYWdlcy4gSW4gc2hvcnQsIHRvIGdldCBhY2Nlc3MgdG8gdGhlaXIgc2NpZW50aSBjIHBhcGVycywgb25lIGhhdmUgdG8gcHJvdmUgeW91cnNlbGYgZWxpZ2libGUgYW5kIHdvcnRoeSwgaS5lLiBzb2x2ZSBhIG1hdGhlbWF0aWMgcmlkZGxlLjxcL3A+XHJcblxyXG48cD5Ib3dldmVyLCB0aGUgdGVzdCB0dXJuZWQgb3V0IGRpXHUwMDBlY3VsdCBmb3Igc29tZSBtYXRoIFBoRCBzdHVkZW50cyBhbmQgZXZlbiBmb3Igc29tZSBwcm9mZXNzb3JzLiBUaGVyZWZvcmUsIHRoZSBtYXRoIGRlcGFydG1lbnQgd2FudHMgdG8gd3JpdGUgYSBoZWxwZXIgcHJvZ3JhbSB3aGljaCBzb2x2ZXMgdGhpcyB0YXNrIChpdCBpcyBub3QgaXJyYXRpb25hbCwgYXMgdGhleSBhcmUgZ29pbmcgdG8gbWFrZSBtb25leSBvbiBzZWxsaW5nIHRoZSBwcm9ncmFtKS48XC9wPlxyXG5cclxuPHA+VGhlIHRhc2sgdGhhdCBpcyBwcmVzZW50ZWQgdG8gYW55b25lIHZpc2l0aW5nIHRoZSBzdGFydCBwYWdlIG9mIHRoZSBtYXRoIGRlcGFydG1lbnQgaXMgYXMgZm9sbG93czogZ2l2ZW4gYSBuYXR1cmFsIG4sIGNvbXB1dGU8XC9wPlxyXG5cclxuPHA+XFxbU197bn0gPVxcc3VtIF97IGs9MSB9XnsgbiB9eyBcXGxlZnRbIFxcZnJhY3soM2srNikhKzF9ezNrKzd9LVxcbGVmdFsgXFxmcmFjeygzays2KSF9ezNrKzd9IFxccmlnaHRdICZuYnNwO1xccmlnaHRdICZuYnNwO30gXFxdPFwvcD5cclxuXHJcbjxwPndoZXJlIFt4XSBkZW5vdGVzIHRoZSBsYXJnZXN0IGludGVnZXIgbm90IGdyZWF0ZXIgdGhhbiB4LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIHJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgcXVlcmllcyB0ICh0ICZsZTsgMTA8c3VwPjY8XC9zdXA+KS4gRWFjaCBxdWVyeSBjb25zaXN0IG9mIG9uZSBuYXR1cmFsIG51bWJlciBuKDEgJmxlOyBuICZsZTsgMTA8c3VwPjY8XC9zdXA+KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBuIGdpdmVuIGluIHRoZSBpbnB1dCBvdXRwdXQgdGhlIHZhbHVlIG9mIFM8c3ViPm48XC9zdWI+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==