수열의 점수

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

요약

X와 Y가 주어질 때, 수열 A_k = A_{k-2} - A_{k-1}의 첫 0 이하 항이 가장 늦게 나타나도록 x와 y를 고릅니다.

난이도: 보통10점 중 7점
유형: 수학, 정수론, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

두 정수 $x$ 와 $y$ 가 주어질 때, 무한한 길이의 정수 수열 $A$ 를 아래와 같이 정의한다.

$A_1 = x$
$A_2 = y$
$k \geq 3$ 일 때 $A_k = A_{k-2} - A_{k-1}$

정수 $x$ 와 $y$ 는 $1 \leq x \leq X$ , $1 \leq y \leq Y$ 를 만족하도록 선택할 수 있다.

수열에서 $0$ 이하의 수가 처음 등장하는 항의 번호가 $k$ 일 때, $k$ 를 수열 $A$ 의 점수라고 한다. $x$ 와 $y$ 를 어떻게 정하더라도 수열에 $0$ 이하의 수가 적어도 한 번 등장함을 증명할 수 있다. 수열 $A$ 의 점수를 최대화하는 $x$ 와 $y$ 를 찾아보자.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 두 개의 정수 $X$ , $Y$ 가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스에 대해, 수열 $A$ 의 점수를 최대화하는 $x$ 와 $y$ 를 공백으로 구분하여 출력한다.

정답이 여러 개 존재한다면 그중 아무거나 출력해도 상관없다.

제한

$1\leq T \leq 10^4$
$1\leq X, Y \leq 3 \times 10^5$
모든 테스트 케이스의 $X$ 의 합은 $10^6$ 을 넘지 않는다
모든 테스트 케이스의 $Y$ 의 합은 $10^6$ 을 넘지 않는다

예제1

예제 1
입력
```
1
4 3
```
예상 출력
```
4 3
```