뒤집고 자르기 (Hard)

탁자 위에 원 모양의 종이가 놓여 있다. 원의 윗면은 전부 검은색이고 아랫면은 전부 흰색이다. 원의 둘레 길이는 양의 정수 $c$이다.

가위로 원을 자른다. 먼저 원의 둘레 위에서 임의의 점 하나를 고르고, 그 점을 활성점이라고 부른다. 활성점에서 원의 중심까지 직선으로 자른다.

다음으로 $s < c^2$인 양의 정수 $s$를 고른다. $s$는 걸음 길이의 제곱이다. 이후 무한히 라운드를 반복한다. 각 라운드는 다음 단계로 이루어진다.

1. 현재 활성점에서 둘레를 따라 반시계 방향으로 $\sqrt{s}$만큼 간 점을 새 점으로 찾는다.
2. 새 점에서 원의 중심까지 직선으로 자른다.
3. 활성점에서 난 절단선에서 시작해 반시계 방향으로 새 점에서 난 절단선까지 이어지는 부채꼴이 생긴다. 부채꼴 안에는 다른 절단선이 있을 수도 있다.
4. 부채꼴 전체를 탁자에서 들어 올려 위아래를 뒤집은 뒤 제자리에 되돌려 놓는다. 부채꼴이 여러 조각으로 나뉘어 있었다면 이 과정에서 조각들의 순서가 거꾸로 된다.
5. 새 점이 다음 라운드의 활성점이 된다.

유한 번의 라운드 뒤에 원이 다시 전부 검은색이 되는 $(c, s)$ 쌍을 모두 찾고, 각 쌍에 대해 그렇게 되는 최소 라운드 수를 구하라. 윗면의 모든 점이 검은색이거나 절단선 위에 있으면 원은 전부 검은색이다. 절단선 위에 놓인 점의 색은 고려하지 않아도 된다.

첫 줄에 테스트 케이스의 수 $t$가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다. 각 테스트 케이스는 양의 정수 $c$와 $s$가 한 줄에 주어진다. $s < c^2$이고 $c \le 10^6$이라고 가정해도 된다.

원이 다시 전부 검은색이 되지 않으면 never를 한 줄에 출력한다. 그렇지 않으면 원이 다시 전부 검은색이 되는 최소 양의 라운드 수를 한 줄에 출력한다.

첫 번째 예제는 둘레가 360인 원에서 한 번에 둘레의 60단위씩 담긴 부채꼴을 뒤집는 경우다. 여섯 라운드 뒤에는 모든 부분이 정확히 한 번씩 뒤집히고, 다시 여섯 라운드가 지나면 처음 상태로 돌아간다.

두 번째 예제는 위 그림의 상황에 해당한다. 원이 전부 검은색으로 돌아가는 데 24라운드가 걸린다.

세 번째 예제에서는 매 라운드마다 원의 5/6을 뒤집는다. 놀랍게도 네 라운드만 지나면 원이 다시 전부 검은색이 된다.