시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3775 2571 2161 69.642%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

2
5
100

예제 출력 1

2
10
W3sicHJvYmxlbV9pZCI6IjYzNTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5Y2NcdWNkZThcdWQ1NWMgXHVjMGMxXHViYzk0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMWNcdWFjMTVcdWIzMDBcdWQ1NTlcdWFkNTAgXHVhY2U0XHVjNzkwXHVhYzAwIFx1YWUzMFx1YzIxOVx1YzBhY1x1Yzc1OCBcdWM5YzBcdWQ1NThcdWM1ZDBcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWJjMjlcdWM3NzQgXHVjNzdjXHViODJjXHViODVjIFx1YjI5OFx1YzViNFx1YzEyMCBcdWFjMTBcdWM2MjVcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViYzI5XHVjNWQwXHViMjk0IFx1YmM4Y1x1YzgxMFx1Yzc0NCBcdWI5Y2VcdWM3NzQgXHViYzFiXHVjNzQwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWFkNmNcdWFlMDhcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdlY1x1YjM1OCBcdWM1YjRcdWIyOTBcdWIwYTAsIFx1YWMxMFx1YzYyNSBcdWFjMDRcdWMyMThcdWM3NzggXHVjMGMxXHViYzk0XHVjNzc0XHViMjk0IFx1YzljMFx1YjhlOFx1ZDU1YyBcdWIwOThcdWJhMzhcdWM5YzAgXHVjODE1XHVjMmUwXHViMDk4XHVhYzA0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWFlMzBcdWI4NWMgXHVhY2IwXHVjODE1XHVkNTg4XHViMmU0LiBcdWFjOGNcdWM3ODRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWI3N2NcdWM2YjRcdWI0ZGNcdWM1ZDBcdWMxMWMgXHVjMGMxXHViYzk0XHVjNzc0XHViMjk0IFx1YzcwNFx1YzJhNFx1ZDBhNFx1Yjk3YyBcdWQ1NWMgXHVjNzk0IFx1YjRlNFx1Yzc3NFx1ZDBhNFx1YWNlMCwgXHViMmVjXHViODI0XHVhYzAwXHViYTcwIFx1YWMxMFx1YzYyNVx1Yzc0NCBcdWQ1NWMgXHVhYzFjXHVjNTI5IFx1YmFhOFx1YjQ1MCBcdWM1ZjBcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHViNzdjXHVjNmI0XHViNGRjXHVjNWQwXHVjMTFjXHViMjk0IDIsIDQsIDYsIC4uLiBcdWJjODggXHViYzI5XHVjNzQ0IFx1YjJlNFx1YzJkYyBcdWM3YTBcdWFkZjhcdWFjZTAsIFx1YzEzOCBcdWJjODhcdWM5ZjggXHViNzdjXHVjNmI0XHViNGRjXHVjNWQwXHVjMTFjXHViMjk0IDMsIDYsIDksIC4uLiBcdWJjODggXHViYzI5XHVjNzc0IFx1YzVmNFx1YjgyNFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM3YTBcdWFkZjhcdWFjZTAsIFx1YzdhMFx1YWNhOFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWM1ZjBcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgblx1YmM4OFx1Yzc1OCBcdWI3N2NcdWM2YjRcdWI0ZGNcdWI5N2MgXHVjOWM0XHVkNTg5XHVkNTVjIFx1Yzc3NFx1ZDZjNCwgXHVjMGMxXHViYzk0XHVjNzc0XHViMjk0IFx1YzcwNFx1YzJhNFx1ZDBhNFx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViY2QxXHVjNzQ0IFx1YjljOFx1YzJkY1x1YWNlMCBcdWM0ZjBcdWI3ZWNcdWM4MzggXHVjN2EwXHViNGUwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkNmNcdWFlMDhcdWI0MThcdWM1YjRcdWM3ODhcdWIyOTQgXHViYTg3IFx1YmE4NShcdWM1YjRcdWNhNGNcdWJhNzQgMFx1YmE4NSlcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWJjMjlcdWM3NDQgXHVjN2EwXHVhZGY4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWNjNDQgXHVjMGMxXHViYzk0XHVjNzc0XHVhYzAwIFx1YzRmMFx1YjdlY1x1YzgzOFx1YmM4NFx1YjgzOFx1YjJlOCBcdWFjODNcdWM3NDQgXHVhZTY4XHViMmViXHVhY2UwIFx1Yzk4OVx1YzJkYyBcdWIzYzRcdWI5ZGRcdWNlNWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMyOVx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYTg3IFx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHViM2M0XHVjOGZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1YyBcdWFjMWNcdWM1MjkgXHViYzI5XHVjNzU4IFx1YWMxY1x1YzIxOCBuKDUmbGU7biZsZTsxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1YyBcdWFjMWNcdWM1MjkgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViMmY1LCBcdWM5ODkgXHViYTg3IFx1YmE4NVx1Yzc3NCBcdWQwYzhcdWNkOWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjM1OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBEcnVuayBKYWlsZXIiLCJkZXNjcmlwdGlvbiI6IjxwPkEgY2VydGFpbiBwcmlzb24gY29udGFpbnMgYSBsb25nIGhhbGwgb2YgbiBjZWxscywgZWFjaCByaWdodCBuZXh0IHRvIGVhY2ggb3RoZXIuIEVhY2ggY2VsbCBoYXMgYSBwcmlzb25lciBpbiBpdCwgYW5kIGVhY2ggY2VsbCBpcyBsb2NrZWQuPFwvcD5cclxuXHJcbjxwPk9uZSBuaWdodCwgdGhlIGphaWxlciBnZXRzIGJvcmVkIGFuZCBkZWNpZGVzIHRvIHBsYXkgYSBnYW1lLiBGb3Igcm91bmQgMSBvZiB0aGUgZ2FtZSwgaGUgdGFrZXMgYSBkcmluayBvZiB3aGlza2V5LCBhbmQgdGhlbiBydW5zIGRvd24gdGhlIGhhbGwgdW5sb2NraW5nIGVhY2ggY2VsbC4gRm9yIHJvdW5kIDIsIGhlIHRha2VzIGEgZHJpbmsgb2Ygd2hpc2tleSwgYW5kIHRoZW4gcnVucyBkb3duIHRoZSBoYWxsIGxvY2tpbmcgZXZlcnkgb3RoZXIgY2VsbCAoY2VsbHMgMiwgNCwgNiwgJmhlbGxpcDspLiBGb3Igcm91bmQgMywgaGUgdGFrZXMgYSBkcmluayBvZiB3aGlza2V5LCBhbmQgdGhlbiBydW5zIGRvd24gdGhlIGhhbGwuIEhlIHZpc2l0cyBldmVyeSB0aGlyZCBjZWxsIChjZWxscyAzLCA2LCA5LCAmaGVsbGlwOykuIElmIHRoZSBjZWxsIGlzIGxvY2tlZCwgaGUgdW5sb2NrcyBpdDsgaWYgaXQgaXMgdW5sb2NrZWQsIGhlIGxvY2tzIGl0LiBIZSByZXBlYXRzIHRoaXMgZm9yIG4gcm91bmRzLCB0YWtlcyBhIGZpbmFsIGRyaW5rLCBhbmQgcGFzc2VzIG91dC48XC9wPlxyXG5cclxuPHA+U29tZSBudW1iZXIgb2YgcHJpc29uZXJzLCBwb3NzaWJseSB6ZXJvLCByZWFsaXplcyB0aGF0IHRoZWlyIGNlbGxzIGFyZSB1bmxvY2tlZCBhbmQgdGhlIGphaWxlciBpcyBpbmNhcGFjaXRhdGVkLiBUaGV5IGltbWVkaWF0ZWx5IGVzY2FwZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIG51bWJlciBvZiBjZWxscywgZGV0ZXJtaW5lIGhvdyBtYW55IHByaXNvbmVycyBlc2NhcGUgamFpbC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIuIFRoaXMgaXMgdGhlIG51bWJlciBvZiBsaW5lcyB0aGF0IGZvbGxvdy4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIGxpbmVzIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgYmV0d2VlbiA1IGFuZCAxMDAsIGluY2x1c2l2ZSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBjZWxscyBuLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGxpbmUsIHlvdSBtdXN0IHByaW50IG91dCB0aGUgbnVtYmVyIG9mIHByaXNvbmVycyB0aGF0IGVzY2FwZSB3aGVuIHRoZSBwcmlzb24gaGFzIG4gY2VsbHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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