크기 $n$인 채유 유리가 공중에서 떨어져 영롱한 결정 조각들로 부서졌으며, 각 조각의 크기는 모두 양의 정수입니다.

아야는 이 반짝이는 결정 조각들을 가볍게 집어 들었습니다. 그녀의 눈에 크기가 $x$인 결정 조각은 $x$가 1보다 큰 홀수일 때만 '아름다운 결정 조각'으로 보입니다.

모든 결정 조각이 아름다운 결정 조각이라는 전제하에, 아야는 결정 조각 개수의 최댓값을 알고 싶어 합니다. 모든 결정 조각이 아름다운 결정 조각인 경우가 존재하지 않는다면 -1을 출력하십시오.

입력

본 문제는 여러 개의 테스트 케이스로 구성되어 있습니다. 첫 번째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10^4$)가 주어집니다.

각 테스트 케이스마다: 한 줄에 하나의 양의 정수 $n$ ($1 \le n \le 10^9$)이 주어집니다. 이는 채유 유리의 크기, 즉 모든 결정 조각의 크기 합을 의미합니다.

출력

각 테스트 케이스마다: 모든 결정 조각이 아름다운 결정 조각일 때, 결정 조각 개수의 최댓값을 한 줄에 출력하십시오. 만약 모든 결정 조각이 아름다운 결정 조각인 경우가 존재하지 않는다면 -1을 출력하십시오.

예제

입력 1

6
1
3
5
7
8
9

출력 1

-1
1
1
1
2
3

참고 1

$n = 3$, $n = 5$, $n = 7$일 때, 결정 조각의 최대 개수는 명백히 1입니다. $n = 8$일 때, 결정 조각의 최대 개수는 2이며, 이때 결정 조각의 크기는 각각 3, 5입니다. $n = 9$일 때, 결정 조각의 최대 개수는 3이며, 이때 결정 조각의 크기는 각각 3, 3, 3입니다.