題目描述

給定一個正整數$x$，有兩種詢問：

1. 求一個正整數$y$，滿足$2 \le y \le x - 1$且$x \bmod y$最小，如果有多解，求出最小的$y$
2. 求一個正整數$y$，滿足$2 \le y \le x - 1$且$x \bmod y$最大，如果有多解，求出最小的$y$

輸入格式

第一行一個正整數$T$，表示有$T$組數據、

接下來$T$行，每行兩個整數$x$和$k$，如果$k=0$，表示回答第一種詢問；如果$k=1$，表示回答第二種詢問。

輸出格式

對於每組數據，輸出一行一個整數，表示答案。

Samples

2
4 0
5 1

2
3

提示

對於前$30\%$的數據，$x \le 10^5$。

對於另外$20\%$的數據，$k=0$。

對於另外$20\%$的數據，$k=1$。

對於所有數據，$1 \le T \le 100$，$3 \le x \le 10^9$，$0 \le k \le 1$

原始資料

• Zero1 題號：b112
• Hydro 題號：Z1112
• Locale：zh_TW
• Display：practice