너드 스나이핑

(출처: xkcd)

횡단보도를 건너던 물리학자는 이 문제를 해결하지 못했습니다! 여러분은 해결할 수 있을까요?

여러분이 해결해야 하는 문제는 다음과 같습니다.

저항값이 $1\,\Omega$인 이상적인 저항이 무한히 연결된 2차원 정사각 격자 회로가 있습니다. 이 격자에서 저항 4개가 연결된 점 하나를 임의로 골라 좌표 $(0,0)$으로 정합니다. 그 점에서 저항이 연결된 방향을 따라 가로축과 세로축을 정하고, 이 축을 기준으로 나머지 점들의 좌표를 정합니다. 예를 들어 $(0,0)$에서 오른쪽으로 저항 3개, 위쪽으로 저항 2개만큼 떨어진 점은 $(3,2)$로 나타냅니다. 정수 좌표 $(x,y)$가 주어지면, $(0,0)$과 $(x,y)$ 사이의 등가 저항을 계산해야 합니다.

흥미롭게도, 이 문제의 정답은 모든 $(x,y)$에 대해 $\displaystyle \frac{s}{t}+\frac{2}{\pi} \frac{u}{v}$ ($\displaystyle \frac{s}{t}$와 $\displaystyle \frac{u}{v}$는 유리수)의 꼴로 유일하게 표현할 수 있음을 증명할 수 있습니다. 또한 이 문제의 조건 아래에서, 모든 정답에 대해 $at \equiv s \pmod{998244353}$이고 $bv \equiv u \pmod{998244353}$인 정수 $0 \le a,b < 998244353$가 각각 하나씩 존재함이 보장됩니다. 여러분은 이 조건을 만족하는 두 정수 $a$와 $b$를 찾아 출력해야 합니다.

과연 여러분은 이 문제를 해결할 수 있을까요?

첫 번째 줄에 테스트 케이스의 수 $T$가 주어집니다. ($0 < T \le 10^5$)

두 번째 줄부터 $T+1$번째 줄까지 각 줄에 정수 $x$와 $y$가 공백으로 구분되어 주어집니다. ($-2000 \le x,y \le 2000$)

각 테스트 케이스마다 문제에서 설명한 정답에 대응하는 두 정수 $a$와 $b$를 공백으로 구분하여 한 줄에 출력하세요.

이 노트는 문제를 푸는 데 필요한 물리 지식과 조건을 정리합니다.

• 단위: $\text{V}$, $\text{A}$, $\Omega$는 각각 전압, 전류, 저항의 단위입니다. 별도의 언급이 없으면 상수나 식 뒤에 이 기호나 문자가 붙어 있을 때 그 단위를 씁니다.
• 전압과 전위: 회로의 한 점에 $v\,\text{V}$의 전압을 가하고, 이 점과 전선으로 연결된 점 하나를 접지합니다. 이때 전압을 가한 점의 전위는 $v\,\text{V}$, 접지한 점의 전위는 $0\,\text{V}$가 됩니다. 전지를 쓰는 경우에는 보통 +극을 전압 공급원, -극을 접지로 보고 설명하지만, 정확히 설명하려면 전압 공급원과 접지를 나누어 생각하는 것이 좋습니다.
• 전위차: 앞의 예에서 전압을 가한 점과 접지한 점의 전위 차이는 $v\,\text{V}$입니다. 이를 두고 "두 점 사이의 전위차가 $v\,\text{V}$이다"라고 합니다.

그림 1. 전압 공급원과 접지 사이의 전위차가 $5\,\text{V}$인 회로도입니다.

• 저항과 전류: 전압 공급원과 접지 사이의 전위차가 $v\,\text{V}$이고 $r\,\Omega$의 저항이 있으면, 옴의 법칙 $V=IR$에 따라 두 점 사이의 전류는 $(v/r)\,\text{A}$입니다. 회로도에서 저항은 지그재그 기호로 그립니다. 별도로 언급하지 않으면 저항이 아닌 전선에는 저항이 없다고 전제합니다.

그림 2. 전위차가 $5\,\text{V}$이고 저항이 $2\,\Omega$이면, 전류는 $V/R = 5/2\,\text{A}$로 계산됩니다.

• 직렬 연결: 세 점 $a$, $b$, $c$가 있고 $a$와 $b$를 잇는 저항 하나, $b$와 $c$를 잇는 저항 하나가 있을 때, $a$와 $c$ 사이의 저항 연결 방식을 직렬 연결이라고 합니다. 두 저항 $R_1$과 $R_2$가 직렬로 연결되면 합성 저항은 $R=R_1+R_2$입니다. 예를 들어 $3\,\Omega$ 저항과 $2\,\Omega$ 저항을 직렬로 연결하면 합성 저항은 $5\,\Omega$가 됩니다.

그림 3. 직렬 연결의 예입니다. 그림에서 $a$와 $c$ 사이의 저항 연결 방식을 직렬 연결이라고 합니다.

• 병렬 연결: 두 점 $a$, $b$ 사이를 저항 두 개가 잇고 있을 때, $a$와 $b$ 사이의 저항 연결 방식을 병렬 연결이라고 합니다. 두 저항 $R_1$과 $R_2$가 병렬로 연결되면 합성 저항은 $1/R=1/R_1+1/R_2$입니다. 예를 들어 $3\,\Omega$ 저항과 $2\,\Omega$ 저항을 병렬로 연결하면 합성 저항은 $\frac{1}{1/3+1/2}=6/5\,\Omega$가 됩니다.

그림 4. 병렬 연결의 예입니다. 그림에서 $a$와 $b$ 사이의 저항 연결 방식을 병렬 연결이라고 합니다.

• 단순한 회로의 합성 저항: 직렬 연결과 병렬 연결만으로 이루어진 단순한 회로 전체의 합성 저항은, 병렬로 연결된 저항들을 그에 대응하는 저항 하나로 바꾸고, 직렬로 연결된 저항을 다시 그에 대응하는 저항 하나로 바꾸는 과정을 반복해서 구합니다.

그림 5. 단순한 회로의 합성 저항을 계산하는 방법의 예입니다.

• 키르히호프 전압 법칙: 하나의 폐회로(그래프의 사이클과 같은 개념입니다)에서 전위차의 합은 $0$입니다. 즉, 한 점에서 출발해 사이클을 한 바퀴 돌아 출발점으로 돌아오면, 그 경로에서 지난 모든 전위차의 합은 $0$입니다. 이때 전류의 흐름과 반대 방향으로 지나면 전위차를 음수로 취급합니다.
• 키르히호프 전류 법칙: 한 정점을 기준으로 들어오고 나가는 전류의 합은 $0$입니다. 즉, 어떤 정점으로 들어오는 전류의 합과 나가는 전류의 합은 같습니다.
• 전류 분배 법칙: 여러 저항이 병렬로 연결되어 있으면, 키르히호프 전압 법칙에 따라 모든 저항 쌍에 걸리는 전위차는 같아야 합니다. (각 저항 쌍이 하나의 폐회로를 이루기 때문입니다.) 또한 옴의 법칙에 따라 전위차가 같을 때 각 저항에 흐르는 전류의 크기는 저항에 반비례합니다. 마지막으로 키르히호프 전류 법칙에 따라 각 저항으로 흐른 전류의 합은 전체 전류와 같아야 합니다. 따라서 각 저항에 흐르는 전류는 전체 저항으로 계산한 전류를 저항에 반비례하게 나눈 값입니다.

그림 6. 병렬로 연결된 저항 두 개에 전류 분배 법칙을 적용한 예입니다.

• 전압 분배 법칙: 여러 저항이 직렬로 연결되어 있으면, 키르히호프 전류 법칙에 따라 각 저항에 흐르는 전류는 같아야 합니다. (인접한 저항 사이의 정점에서 흐르는 전류의 합이 $0$이기 때문입니다.) 또한 옴의 법칙에 따라 전류가 같을 때 각 저항에 걸리는 전압의 크기는 저항에 비례합니다. 따라서 각 저항에 걸리는 전압은 전체 저항으로 계산한 전위차를 저항에 비례하게 나눈 값입니다.

그림 7. 직렬로 연결된 저항 두 개에 전압 분배 법칙을 적용한 예입니다.

• 등가 저항: 전압 공급원, 접지, 전선, 저항만으로 구성된 임의의 회로 일부를 어떤 저항 하나로 바꿨을 때 나머지 부분의 전위와 전류가 변하지 않는다면, 그 저항의 크기를 $r\,\Omega$라고 합니다. 이를 두고 "이 회로 일부의 등가 저항이 $r\,\Omega$이다"라고 합니다.

이제 이 지식으로 유한한 회로에서 전압 공급원부터 접지된 점까지의 등가 저항을 구할 수 있습니다. 유한한 회로의 등가 저항 계산은 이 문제에서 직접 연습할 수 있습니다.

하지만 이 문제는 유한한 회로를 다루지 않습니다. 그래서 위에서 주어진 조건만으로는 문제의 회로를 완전히 분석할 수 없습니다. 따라서 이 노트에서는 유한한 회로를 이용해 문제를 정의하는 방법을 설명합니다.

• $C_n$을 문제의 회로와 전체 모양이 같고, 중심이 $(0,0)$이며 한 변의 저항 개수가 $2n$개인 유한한 정사각 격자 회로로 정의합니다.
• $R_n(x,y)$를 $n \ge |x|$이고 $n \ge |y|$일 때, $C_n$에서 $(0,0)$과 $(x,y)$ 사이의 등가 저항으로 정의합니다.
• $n$이 무한대로 발산할 때, 등가 저항 $\lim_{n \to \infty} R_n(x,y)$는 위 문제에서 설명한 조건을 만족하는 값 $R$로 수렴합니다.
• 이 값 $R$에 따라 문제에서 설명한 대로 두 정수 $a$, $b$를 출력하면 됩니다.