P5434. 整除最少操作

场次：2026年9月12日 · 来源：CodeFun2000 P5434

题目描述

有两个正整数 $n$、$m$。每一次操作，从二者中任选一个，将其加一或减一；操作结束后该数仍须为正整数。

求最少操作次数，使得最终有 $n \mid m$（即 $m$ 能被 $n$ 整除）。

输入格式

每个测试文件包含多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 10^4$），表示数据组数。每组测试数据如下：

一行两个正整数 $n$、$m$（$1 \le n, m \le 10^6$）。

输出格式

对每组数据输出一行一个整数，表示使 $n$ 整除 $m$ 的最少操作次数。

示例

示例 1

输入：

4
4 15
11 25
7 7
10 7

输出：

1
2
0
3

说明：

• $4,15$：把 $m$ 加到 $16$，则 $4 \mid 16$，共 $1$ 次。把 $n$ 改成 $3$ 或 $5$ 同样只需 $1$ 次。
• $11,25$：把 $n$ 改成 $12$、$m$ 改成 $24$，则 $12 \mid 24$，共 $2$ 次。只把 $m$ 减到 $22$ 要 $3$ 次，更差。
• $7,7$：已有 $7 \mid 7$，答案为 $0$。
• $10,7$：把两者都改成 $7$（或都改成 $10$）需要 $3$ 次；更少次数无法整除。