#2555 I Love Chocolate

1 s   64 MB  

Description

동원이는 상자에 담긴 초콜릿을 먹으려고 했 으나, 이빨이 썩는다며 엄마에게 혼이 났다. 우 는 동원이에게 엄마는 퀴즈를 내어 그에 상응하 는 개수의 초콜릿을 주기로 하였다. 초콜릿이 N개 있다면, 동원이는 1부터 N까지의 수 중 하나를 선택해야 한다. 이때, N을 동원이 가 선택한 수로 나누었을 때, 그 나머지만큼 초 콜릿을 얻을 수 있다. 기회는 한 번뿐일 때, 어 떤 수를 말해야 가장 많은 초콜릿을 얻을 수 있 을까? 예를 들어 초콜릿이 3개 있을 때, 1 또는 3을 선택한다면 나머지가 0이 되므로 초콜릿을 얻을 수 없다. 그러나, 2를 선택한다면 나머지가 1이 되므로 1개의 초콜릿을 얻을 수 있다.

Input

입력의 첫 번째 줄은 테스트 케이스의 개수 T ( 1 <= T <= 100,000)가 주어지며, 각테스트 케 이스는 한 줄에 하나씩 초콜릿의 개수 N이 입력된다. ( 1<= N <= 100,000, N은 정수 )

Output

각 테스트 케이스에 대해서, 동원이가 가장 많은 초콜릿을 받기 위해 선택해야 하는 수를 한 줄에 하나씩 출력한다. 만약 만족하는 답이 여러 개일 경우 가장 작은 수를 출력하며, 초콜릿을 받을 수 없을 때에는 ‘T_T’를 출력한다.

Sample Input

Sample Output

3
2
4
5
T_T
3
3

Source

2007 Soongsil University Campus Programming Contest, test data : Kogle