34669번 - 가희와 노선 건설 놀이 2

문제

가희는 쿠마시의 시장입니다. 쿠마시에는 쿠마역과 모토역을 지나는 쿠마선이 있고, 추가로 $k$개의 역을 건설할 예정입니다. 가희는 이 $k$개의 역을 쿠마역과 모토역으로 연결하고자 합니다. $k$개의 역은 다음 조건들을 모두 만족해야 합니다.

• $k$개의 역은 환승역이 아닙니다.
• $k$개의 역은 가희가 건설할 하나 이상의 노선에 속합니다.

또한 가희가 건설할 노선들은 다음 조건들을 모두 만족해야 합니다.

• 기점은 쿠마역이고 종점은 모토역입니다.
• 쿠마역과 모토역을 제외하고 최소 하나 이상의 역이 있습니다.
• 수요 기대 상수는 $c$입니다.

노선 $X$의 수요 기대 상수는 노선 $X$에 있는 비환승역의 개수와 노선 $X$의 기대 수요의 곱으로 정의합니다. 또한 쿠마역과 모토역은 환승역입니다.

질문이 $Q$개 주어집니다. 각 질문마다 $c$와 $k$가 주어졌을 때, 가희가 건설할 노선들의 기대 수요의 합이 가질 수 있는 최댓값과 최솟값을 구해 주세요.

입력

첫 번째 줄에 질문의 개수 $Q$가 주어집니다.

두 번째 줄부터 $Q$개의 줄에 걸쳐 $c,ドル $k$가 공백으로 구분되어 주어집니다. 이때, $c$는 $k$의 배수입니다.

출력

$Q$개의 줄에 걸쳐 가희가 건설할 노선들의 기대 수요 합이 가질 수 있는 최댓값과 최솟값을 공백으로 구분하여 한 줄에 하나씩 출력해 주세요.

답이 정수인 경우, 정수 부분만 출력해 주세요. 소수점 이하를 출력하면 오답으로 처리됩니다.

제한

• 1ドル \leq Q \leq 10^{5}$
• 1ドル \leq c \leq 10^{5}$
• 1ドル \leq k \leq 10^{5}$
• 입력으로 주어지는 모든 수는 정수입니다.

노트