yyym说到：我吃过的苦你们也得给我吃....
-----2023.3.29
一共有 t(1 \le t\le50) 组询问， 给你两个数 p(1 \le p \le 10^{18}) 和 q(2\le q\le 10^9) ，问最大的 x 是多少可以使得：
输入
第一行代表总共的测试样例 t
之后每个样例第一个为 p ， 第二个为 q
输出
见样例
样例
| 标准输入 复制文本 |
3 10 4 12 6 179 822 |
| 标准输出 复制文本 |
10 4 179 |
| 标准输入 复制文本 |
10 246857872446986130 713202678 857754240051582063 933416507 873935277189052612 530795521 557307185726829409 746530097 173788420792057536 769449696 101626841876448103 132345797 598448092106640578 746411314 733629261048200000 361714100 981271355542147402 38 559754147245184151 431517529 |
| 标准输出 复制文本 |
123428936223493065 918940509 37932865019708 1 57929473597352512 767888699 299224046053320289 31896924393400000 490635677771073701 26946235365387 |
| 标准输入 复制文本 |
10 228282288 228282288 1000000000000000000 1000000000 1244094302301841 35271721 998005893107997601 999002449 999999874000003969 999999937 956980859148255595 5 1 323 1 1000000000 424001357601318819 537974673 100000000 1000000000 |
| 标准输出 复制文本 |
114141144 976562500000000 5939 31607 1 191396171829651119 1 1 424001357601318819 100000000 |