코코는 특이하게 생긴 화이트 초콜릿과 다크 초콜릿을 무한히 많이 갖고 있다. 화이트 초콜릿은 각 변의 길이가 $1$인 사각 피라미드이고, 다크 초콜릿은 각 변의 길이가 $1$인 정사면체 모양이다. 어느 날 코코는 이 초콜릿들을 가지고 놀다가, 초콜릿을 잘 쌓으면 더 큰 사각 피라미드를 만들 수 있다는 사실을 알아냈다. 바닥면의 직사각형의 크기가 $R \times C$인 피라미드를 쌓는 구체적인 방법은 다음과 같다.

1. 먼저 바닥을 $R \times C$개의 화이트 초콜릿으로 채운다.
2. 화이트 초콜릿 사이사이를 다크 초콜릿으로 채운다.
3. 다크 초콜릿 사이의 공간을 다시 화이트 초콜릿으로 채운다. 여기까지 진행하면 위쪽 면은 $(R-1) \times (C-1)$ 크기의 평평한 직사각형이 된다.
4. 윗면의 넓이가 $0$이 될 때까지 반복한다.

아래 그림은 $2 \times 3$ 피라미드의 1층을 채우는 과정을 나타낸 것이다. 1층을 채우는 데에 화이트 초콜릿은 8개, 다크 초콜릿은 7개가 필요하고, 2층까지 합하면 각각 10개, 8개가 필요하다.

코코는 아주 큰 초콜릿 피라미드를 만들어 한별이에게 선물하려고 한다. 이 때 화이트와 다크 초콜릿이 각각 몇 개씩 필요한지 계산해주자.

Input

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄 각각에는 정수 $R$과 $C$의 값이 순서대로 주어진다.

Output

각 테스트 케이스에 대해, 필요한 화이트 초콜릿의 개수와 다크 초콜릿의 개수를 한 줄에 순서대로 출력한다.

Examples

Input 1

2
2 3
10 10

Output 1

10 8
670 660

Note

$1 \le T \le 10^5$, $1 \le R, C \le 10^6$