튕기고 튕기고 튕기고

피델이 원 모양의 고리를 만들었다. 고리의 안쪽 경계면은 빛을 그대로 반사하고, 경계 위의 한 점에 레이저가 놓여 있다. 피델은 레이저에서 나간 빛이 경계에서 정확히 $N$번 반사한 뒤 처음으로 출발점에 돌아오도록 처음 방향을 맞추려고 한다. 처음 방향을 고르는 방법은 몇 가지인가?

입사각과 반사각은 같다. 아래 그림을 참고한다. 그림에 그려진 레이저의 위치는 설명을 위한 예시일 뿐이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스는 정수 $N$ 하나가 적힌 줄 하나로 이루어진다.

제한

• $1 \le T \le 3000$
• $1 \le N \le 10^9$

각 테스트 케이스마다 빛이 정확히 $N$번 반사한 뒤 처음으로 출발점에 돌아오게 하는 처음 방향의 개수를 한 줄에 하나씩 출력한다.

$N = 4$이면 네 번 반사한 뒤 출발점으로 돌아오는 방법이 정확히 4가지다. 아래 그림에 모두 그려져 있다.

$N = 3$이면 세 번 반사한 뒤 출발점으로 돌아오는 방법이 정확히 2가지다.