문제
진욱이는 상자에 담긴 초콜릿을 먹으려고 했으나, 이빨이 썩는다며 엄마에게 혼이 났다. 울고있는 진욱이에게 엄마는 퀴즈를 내어 그에 상응하는 개수의 초콜릿을 주기로 하였다. 초콜릿이 N개 있다면, 진욱이는 1부터 N까지의 수 중 하나를 선택해야 한다. 이때, N을 진욱이 가 선택한 수로 나누었을 때, 그 나머지만큼 초콜릿을 얻을 수 있다. 기회는 한 번뿐일 때, 어떤 수를 말해야 가장 많은 초콜릿을 얻을 수 있을까?
예를 들어 초콜릿이 3개 있을 때, 1 또는 3을 선택한다면 나머지가 0이 되므로 초콜릿을 얻을 수 없다. 그러나, 2를 선택한다면 나머지가 1이 되므로 1개의 초콜릿을 얻을 수 있다.
입력
입력의 첫 번째 줄은 테스트 케이스의 개수 T (1≤T≤100,000)가 주어지며, 각 테스트 케이스는 한 줄에 하나씩 초콜릿의 개수 N이 입력된다. (1≤N≤100,000, N은 정수 )
출력
각 테스트 케이스에 대해서, 진욱이가 가장 많은 초콜릿을 받기 위해 선택해야 하는 수를 한 줄에 하나씩 출력한다.
만약 만족하는 답이 여러 개일 경우 가장 작은 수를 출력하며, 초콜릿을 받을 수 없을 때에는 "T_T"를 출력한다.
예제
3
2
4
5
T_T
3
3
로그인해야 코드를 작성할 수 있어요.