题目描述

给定正整数 $n, k$，我们称实数列 $a_1, a_2, \dots, a_k$ 为关于 $n$ 的 $k$-实数划分当且仅当 $\{a_i\}$ 满足下列条件：

• $\sum_{i=1}^k a_i = n$
• $\forall 1 \le i \le k: 0 \le a_i \le n$

记 $n$ 的所有 $k$-实数划分构成的集合为 $D_k(n)$。

对于实数 $x$，我们定义 $[x]$ 为不大于 $x$ 的最大整数，并定义 $x$ 的小数部分为 $\{x\} = x - [x]$。定义四舍五入函数如下：

$$r(x) = \begin{cases} [x] & , \{x\} < 0.5 \\ [x] + 1 & , \{x\} \ge 0.5 \end{cases}$$

试求下述两式的值：

$$\min_{a \in D_k(n)} \left\{ \sum_{i=1}^k r(a_i) \right\}, \quad \max_{a \in D_k(n)} \left\{ \sum_{i=1}^k r(a_i) \right\}$$

---

输入格式

本题包含多组数据。

• 第一行包含一个整数 $T$（$1 \le T \le 10^5$），表示数据组数。
• 对于每组数据： 一行包含两个正整数 $n, k$（$1 \le n, k \le 10^9$）。

---

输出格式

对于每组数据： 输出一行包含两个整数，依次为 $\min_{a \in D_k(n)} \left\{ \sum_{i=1}^k r(a_i) \right\}$ 以及 $\max_{a \in D_k(n)} \left\{ \sum_{i=1}^k r(a_i) \right\}$ 的值。

Samples

5
1 3
4 1
2 2
3 7
4 3

0 2
4 4
2 3
0 6
3 5

Limitation

1s, 1024KiB for each test case.