33468번 - Bee Tea 서브태스크스페셜 저지

문제

COVID-19 바이러스에 이어 KOVID-22 바이러스가 발생하였다!

KOVID-22 바이러스에 감염이 된 사람들은 국가 차원에서 특별 관리하기로 했다. 감염된 사람들은 각자 한 명당 하나의 방에 격리되는데, 방들은 직선 형태의 복도에 배치되어 있고, 정수 $i$에 대하여 $i$번 방은 $i$ 이상 $i+1$ 미만의 좌표 범위를 의미한다. 감염된 사람들은 1ドル$번 방부터 2ドル$번 방, 3ドル$번 방과 같이 방의 번호가 커지는 순서대로 차례로 격리되며, 0ドル$번 방에는 격리 시설의 관리자 동우와 재우가 있다.

KOVID-22 바이러스의 경우 벌집에서 추출한 꿀로 만든 차를 마셔야 금방 낫기 때문에 동우와 재우는 벌꿀차를 만들어 격리자들에게 나누어 주려 한다. 동우와 재우는 각자 보폭에 맞추어 벌꿀차를 나누어 주는데 동우의 보폭은 $A,ドル 재우의 보폭은 $B$이다. 구체적으로 동우와 재우는 각자 0ドル$의 좌표에서 출발해 독립적으로 다음과 같이 벌꿀차를 나누어 준다.

1. 먼저 현재 위치에서 오른쪽(양의 방향)으로 각자 보폭만큼 움직인다.
2. 움직인 후 위치한 방에 격리자가 있는지 여부에 따라 다음을 시행한다.
   • 격리자가 있다면 벌꿀차를 준다. 동우나 재우는 제자리에서 이 행동을 하므로 위치가 변하지 않는다. 이후 1번 행동으로 돌아가 반복한다.
   • 격리자가 없다면 행동을 종료한다.

이때 격리자들의 불만이 생길 수 있으므로, 벌꿀차를 두 번 이상 받거나 한 번도 받지 못하는 격리자는 없도록 하고 싶다. 또한, 격리자가 몇 명이나 될지 모르기 때문에, 아무리 많은 사람이 오더라도 격리자들의 불만이 생기지 않도록 동우와 재우는 보폭을 서로 맞추려 한다. 동우의 보폭이 $A$일 때, 이 조건을 만족하도록 재우의 보폭을 정해보자. 단, 보폭이 1ドル$ 미만이라면, 0ドル$번 방을 거치게 되므로, 보폭이 1ドル$ 이상이라고 하자.

입력

첫 번째 줄에 테스트 케이스의 개수 $T(1\le T\le 10^5)$가 주어진다.

각 테스트 케이스의 첫 번째 줄에 동우의 보폭을 제곱한 값을 의미하는 양의 정수 $A^2(1\le A^2\le 10^{18})$이 주어진다.

모든 테스트 케이스는 서로 다르며, $A^2$이 증가하는 순서대로 주어진다.

출력

각 테스트 케이스 별로 첫 번째 줄에 재우의 보폭 $B$로 가능한 값을 아무거나 하나 출력한다.

단, 정답이 1ドル$ 이상 10ドル^{1,円 000,円 000}$ 이하의 양의 실수 중 존재하지 않는다면 첫 번째 줄에 대신 -1을 출력한다.

출력한 값이 가능한 이론값 중 하나 이상과 절대/상대 오차가 10ドル^{-9}$ 이하라면 정답으로 한다.

제한

서브태스크

힌트