다도해

당신은 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을 출력한다.

• 1 ≤ T ≤ 10
• 2 ≤ N ≤ 1,000
• 1 ≤ Seed, A, B ≤ 1,000,000,000