시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5936 4052 3420 69.597%

문제

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다.

그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

구금되어있는 몇 명(어쩌면 0명)의 학생들은 자신의 방을 잠그지 않은 채 상범이가 쓰러져버렸단 것을 깨닫고 즉시 도망친다.

방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 한 개씩 방의 개수 n(5 ≤ n ≤ 100)이 주어진다.

출력

한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.

예제 입력 1

2
5
100

예제 출력 1

2
10
W3sicHJvYmxlbV9pZCI6IjYzNTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5Y2NcdWNkZThcdWQ1NWMgXHVjMGMxXHViYzk0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMWNcdWFjMTVcdWIzMDBcdWQ1NTlcdWFkNTAgXHVhY2U0XHVjNzkwXHVhYzAwIFx1YWUzMFx1YzIxOVx1YzBhY1x1Yzc1OCBcdWM5YzBcdWQ1NThcdWM1ZDBcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWJjMjlcdWM3NzQgXHVjNzdjXHViODJjXHViODVjIFx1YjI5OFx1YzViNFx1YzEyMCBcdWFjMTBcdWM2MjVcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViYzI5XHVjNWQwXHViMjk0IFx1YmM4Y1x1YzgxMFx1Yzc0NCBcdWI5Y2VcdWM3NzQgXHViYzFiXHVjNzQwIFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWFkNmNcdWFlMDhcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdlY1x1YjM1OCBcdWM1YjRcdWIyOTAgXHViMGEwLCBcdWFjMTBcdWM2MjUgXHVhYzA0XHVjMjE4XHVjNzc4IFx1YzBjMVx1YmM5NFx1Yzc3NFx1YjI5NCBcdWM5YzBcdWI4ZThcdWQ1NWMgXHViMDk4XHViYTM4XHVjOWMwIFx1YzgxNVx1YzJlMFx1YjA5OFx1YWMwNCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHVhZTMwXHViODVjIFx1YWNiMFx1YzgxNVx1ZDU4OFx1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViNzdjXHVjNmI0XHViNGRjXHVjNWQwXHVjMTFjIFx1YzBjMVx1YmM5NFx1Yzc3NFx1YjI5NCBcdWM3MDRcdWMyYTRcdWQwYTRcdWI5N2MgXHVkNTVjIFx1Yzc5NCBcdWI0ZTRcdWM3NzRcdWQwYTRcdWFjZTAsIFx1YjJlY1x1YjgyNFx1YWMwMFx1YmE3MCBcdWFjMTBcdWM2MjVcdWM3NDQgXHVkNTVjIFx1YWMxY1x1YzUyOSBcdWJhYThcdWI0NTAgXHVjNWYwXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1Yjc3Y1x1YzZiNFx1YjRkY1x1YzVkMFx1YzExY1x1YjI5NCAyLCA0LCA2LCAuLi4gXHViYzg4IFx1YmMyOVx1Yzc0NCBcdWIyZTRcdWMyZGMgXHVjN2EwXHVhZGY4XHVhY2UwLCBcdWMxMzggXHViYzg4XHVjOWY4IFx1Yjc3Y1x1YzZiNFx1YjRkY1x1YzVkMFx1YzExY1x1YjI5NCAzLCA2LCA5LCAuLi4gXHViYzg4IFx1YmMyOVx1Yzc3NCBcdWM1ZjRcdWI4MjRcdWM3ODhcdWM3M2NcdWJhNzQgXHVjN2EwXHVhZGY4XHVhY2UwLCBcdWM3YTBcdWFjYThcdWM3ODhcdWIyZTRcdWJhNzQgXHVjNWYwXHViMmU0LiBrXHViYzg4XHVjOWY4IFx1Yjc3Y1x1YzZiNFx1YjRkY1x1YzVkMFx1YzExY1x1YjI5NCBcdWJjODhcdWQ2MzhcdWFjMDAga1x1Yzc1OCBcdWJjMzBcdWMyMThcdWM3NzggXHViYzI5XHVjNzc0IFx1YzVmNFx1YjgyNCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjN2EwXHVhZGY4XHVhY2UwLCBcdWM3YTBcdWFjYTggXHVjNzg4XHViMmU0XHViYTc0IFx1YzVmMFx1YjJlNC4gXHVjNzc0XHViODA3XHVhYzhjIG5cdWJjODhcdWM5ZjggXHViNzdjXHVjNmI0XHViNGRjXHVhZTRjXHVjOWMwIFx1YzljNFx1ZDU4OVx1ZDU1YyBcdWM3NzRcdWQ2YzQsIFx1YzBjMVx1YmM5NFx1Yzc3NFx1YjI5NCBcdWM3MDRcdWMyYTRcdWQwYTRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YmNkMVx1Yzc0NCBcdWI5YzhcdWMyZGNcdWFjZTAgXHVjNGYwXHViN2VjXHVjODM4IFx1YzdhMFx1YjRlMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZDZjXHVhZTA4XHViNDE4XHVjNWI0XHVjNzg4XHViMjk0IFx1YmE4NyBcdWJhODUoXHVjNWI0XHVjYTRjXHViYTc0IDBcdWJhODUpXHVjNzU4IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWM3OTBcdWMyZTBcdWM3NTggXHViYzI5XHVjNzQ0IFx1YzdhMFx1YWRmOFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjYzQ0IFx1YzBjMVx1YmM5NFx1Yzc3NFx1YWMwMCBcdWM0ZjBcdWI3ZWNcdWM4MzhcdWJjODRcdWI4MzhcdWIyZTggXHVhYzgzXHVjNzQ0IFx1YWU2OFx1YjJlYlx1YWNlMCBcdWM5ODlcdWMyZGMgXHViM2M0XHViOWRkXHVjZTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMjlcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmE4NyBcdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YjNjNFx1YzhmY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YzU0Y1x1YzU0NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NWMgXHVhYzFjXHVjNTI5IFx1YmMyOVx1Yzc1OCBcdWFjMWNcdWMyMTggbig1Jm5ic3A7JmxlOyBuICZsZTsgMTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NWMgXHVhYzFjXHVjNTI5IFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YjJmNSwgXHVjOTg5IFx1YmE4NyBcdWJhODVcdWM3NzQgXHVkMGM4XHVjZDljXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjYzNTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgRHJ1bmsgSmFpbGVyIiwiZGVzY3JpcHRpb24iOiI8cD5BIGNlcnRhaW4gcHJpc29uIGNvbnRhaW5zIGEgbG9uZyBoYWxsIG9mIG4gY2VsbHMsIGVhY2ggcmlnaHQgbmV4dCB0byBlYWNoIG90aGVyLiBFYWNoIGNlbGwgaGFzIGEgcHJpc29uZXIgaW4gaXQsIGFuZCBlYWNoIGNlbGwgaXMgbG9ja2VkLjxcL3A+XHJcblxyXG48cD5PbmUgbmlnaHQsIHRoZSBqYWlsZXIgZ2V0cyBib3JlZCBhbmQgZGVjaWRlcyB0byBwbGF5IGEgZ2FtZS4gRm9yIHJvdW5kIDEgb2YgdGhlIGdhbWUsIGhlIHRha2VzIGEgZHJpbmsgb2Ygd2hpc2tleSwgYW5kIHRoZW4gcnVucyBkb3duIHRoZSBoYWxsIHVubG9ja2luZyBlYWNoIGNlbGwuIEZvciByb3VuZCAyLCBoZSB0YWtlcyBhIGRyaW5rIG9mIHdoaXNrZXksIGFuZCB0aGVuIHJ1bnMgZG93biB0aGUgaGFsbCBsb2NraW5nIGV2ZXJ5IG90aGVyIGNlbGwgKGNlbGxzIDIsIDQsIDYsICZoZWxsaXA7KS4gRm9yIHJvdW5kIDMsIGhlIHRha2VzIGEgZHJpbmsgb2Ygd2hpc2tleSwgYW5kIHRoZW4gcnVucyBkb3duIHRoZSBoYWxsLiBIZSB2aXNpdHMgZXZlcnkgdGhpcmQgY2VsbCAoY2VsbHMgMywgNiwgOSwgJmhlbGxpcDspLiBJZiB0aGUgY2VsbCBpcyBsb2NrZWQsIGhlIHVubG9ja3MgaXQ7IGlmIGl0IGlzIHVubG9ja2VkLCBoZSBsb2NrcyBpdC4gSGUgcmVwZWF0cyB0aGlzIGZvciBuIHJvdW5kcywgdGFrZXMgYSBmaW5hbCBkcmluaywgYW5kIHBhc3NlcyBvdXQuPFwvcD5cclxuXHJcbjxwPlNvbWUgbnVtYmVyIG9mIHByaXNvbmVycywgcG9zc2libHkgemVybywgcmVhbGl6ZXMgdGhhdCB0aGVpciBjZWxscyBhcmUgdW5sb2NrZWQgYW5kIHRoZSBqYWlsZXIgaXMgaW5jYXBhY2l0YXRlZC4gVGhleSBpbW1lZGlhdGVseSBlc2NhcGUuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBudW1iZXIgb2YgY2VsbHMsIGRldGVybWluZSBob3cgbWFueSBwcmlzb25lcnMgZXNjYXBlIGphaWwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyLiBUaGlzIGlzIHRoZSBudW1iZXIgb2YgbGluZXMgdGhhdCBmb2xsb3cuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBsaW5lcyBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIGJldHdlZW4gNSBhbmQgMTAwLCBpbmNsdXNpdmUsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgY2VsbHMgbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBsaW5lLCB5b3UgbXVzdCBwcmludCBvdXQgdGhlIG51bWJlciBvZiBwcmlzb25lcnMgdGhhdCBlc2NhcGUgd2hlbiB0aGUgcHJpc29uIGhhcyBuIGNlbGxzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2002 Greater New York Programming Contest B번