다도해 | cho.sh

당신은 N개의 작은 섬으로 이루어진 다도해에 다리를 건설하여 임의의 한 섬에서 임의의 다른 섬으로 도달 가능하게 하고 싶다. 현재는 아무 다리도 없는 상태이다.

섬은 0번 부터 N-1번까지 번호가 붙어있다.

당신은 아래와 같은 알고리즘에 따라 다리를 건설하기로 했다.

세 개의 양의 정수 Seed, A, B 를 고른다. 이후, E[ i ], X[ i ], Y[ i ] 를 아래와 같이 정의한다.
- E[ 1 ] = Seed % N2 그리고 E[ i ] = (E[ i-1 ] * A + B) % N2 (i > 1). (각각의 E[i] 값은 어느 두 섬을 연결하는 다리를 지을지 결정한다.)
- X[ i ] = E[ i ] / N 그리고 Y[ i ] = E[ i ] % N (i ≥ 1).
- 위 두 수식에서 "%" 는 정수 나머지 연산을 나타내는 Modulo 이며, "/"은 정수 나눗셈 연산이다.
오늘부터 1일 후 (즉, 내일) X[ 1 ] 번 섬과 Y[ 1 ]번 섬을 연결하는 다리를 건설한다. 만약 X[ 1 ] = Y[ 1 ]이면 이 날은 건설은 하지 않고 논다.
오늘 부터 i일 후, X[ i ] 번 섬과 Y[ i ] 번 섬을 연결하는 다리를 건설한다. 만약 X[ i ] = Y[ i ] 이거나 이미 두 섬을 잇는 다리가 있다면, 이 날은 건설은 하지 않고 논다.

위 알고리즘에 따라 다리를 건설 할 때, 당신은 오늘 부터 몇 일이 지난 후 (M일 후) 목적을 달성할지 궁금하다.

예를 들어 N = 4, Seed = 2020, A = 2, B = 3 인 경우를 생각해보자.

E[ 1 ] = 2020 % 16 = 4, X[ 1 ] = 4 / 4 = 1, Y[ 1 ] = 4 % 4 = 0. 따라서 (1번섬, 0번섬) 을 잇는 다리를 건설한다.
E[ 2 ] = (4 * 2 + 3) % 16 = 11, X[ 2 ] = 11 / 4 = 2, Y[ 2 ] = 11 % 4 = 3. 따라서 (2번섬, 3번섬)을 잇는 다리를 건설한다.
E[ 3 ] = (11 * 2 + 3) % 16 = 9, X[ 3 ] = 9 / 4 = 2, Y[ 3 ] = 9 % 4 = 1. 따라서 (2번섬, 1번섬)을 잇는 다리를 건설한다.
세 번째 다리를 건설한 후 임의의 한 섬에서 다른 섬으로 도달할 수 있으므로 이 때 M = 3이다.

다른 예로, N = 4, Seed = 2020, A = 3, B = 4 인 경우를 생각해보자.

E[ 1 ] = 2020 % 16 = 4, X[ 1 ] = 4 / 4 = 1, Y[ 1 ] = 4 % 4 = 0. 따라서 (1번섬, 0번섬) 을 잇는 다리를 건설한다.
E[ 2 ] = (4 * 3 + 4) % 16 = 0, X[ 2 ] = 0 / 4 = 0, Y[ 2 ] = 0 % 4 = 0. X,Y 값이 같으므로 다리를 건설하지 않는다.
E[ 3 ] = (0 * 3 + 4) % 16 = 4, X[ 3 ] = 4 / 4 = 1, Y[ 3 ] = 4 % 4 = 0. 이미 다리가 있으므로 다리를 건설하지 않는다.
이 경우, (1번섬, 0번섬)을 잇는 다리 이외에 다른 다리를 건설하지 못한다. 따라서 이 때 위 조건을 만족하는 M은 존재하지 않는다.

입력으로 N, Seed, A, B가 주어졌을 때, 위 조건을 만족하는 M값을 구하여 출력한다. 만약 조건을 만족하는 M값이 없다면 0을 출력한다.

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

각 테스트 케이스는 네 개의 정수가 공백으로 구분되어 주어지는데, 순서대로 N, Seed, A, B 이다.

조건을 만족하는 M이 존재하면 그 중 최소값을 출력하고, 존재하지 않으면 0을 출력한다.