만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

미로 탈출

시간 제한2초메모리 제한1024 MB

요약
방이 N개 일렬로 놓인 미로에서 S번 방부터 E번 방까지 가장 빠르게 가는 경로 중 1번이나 N번 방으로 순간이동하는 횟수의 최솟값을 구합니다.
난이도

보통10점 중 6점

유형
수학, 그리디, 구현
정답자
아직 제출이 없습니다

문제

주원이는 방 탈출을 하던 중 미로에 도착했다. 미로는 일렬로 놓인 NN개의 방으로 이루어져 있으며, ii번 방과 i+1i+1번 방은 서로 인접해 있다 (1≤i<N1 \leq i < N). 각 방에는 스위치가 하나씩 있다. 주원이는 입구가 있는 SS번 방에서 출발해 모든 스위치를 누른 뒤, 출구가 있는 EE번 방으로 이동해 탈출해야 한다.

주원이가 쓸 수 있는 이동 방법은 두 가지다. 첫 번째는 비용 00을 소모해 인접한 방으로 이동하는 것이다. 두 번째는 비용 11을 소모해 11번 또는 NN번 방으로 순간 이동하는 것이다. 두 이동 방법 모두 매번 1만큼의 시간이 걸린다. 스위치를 누르는 데는 시간이 들지 않는다.

방 탈출에서는 시간 관리가 중요하므로, 주원이는 미로를 가장 빠르게 빠져나가는 방법을 찾고자 한다. 가장 빠르게 탈출하는 방법들 가운데 비용이 최소인 방법을 찾아라.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 이어지는 각 줄에는 테스트 케이스마다 NN, SS, EE가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스에 대해 가능한 최소 비용을 한 줄에 출력한다.

제한

  • 1≤T≤1041 \leq T \leq 10^4
  • 2≤N≤1092 \leq N \leq 10^9
  • 1≤S,E≤N1 \leq S, E \leq N
  • S≠ES \neq E
  • 입력으로 주어지는 수는 모두 정수이다.

예제1

  1. 예제 1

    입력
    3
    5 5 1
    3 1 2
    7 3 5
    
    예상 출력
    0
    1
    2