SP21155 MANJFIRE - Manoj and Fire

Manoj 是个热衷于数据加密的极客。不过，他也时常做出一些愚蠢的事情，比如像原始人一样在房间里生火。有一天，他不小心把一张包含敏感信息的纸张扔进了火里。幸运的是，他有这些数据的加密版本。 题目中的每个数字表示满足以下条件的整数对 **A** 和 **B** 的数量：**A < B，且 1 ≤ A, B ≤ N**，并且它们的最大公约数（GCD）商序列与提供的整数序列相匹配。 对于一对整数 **(A, B)**，它们的 GCD 商序列是通过使用欧几里得算法来计算 **A** 和 **B** 的最大公约数时得到的商序列。例如： $$\text{GCD}(7, 9) = 2, 1$$

第一行包含一个整数 **T**，表示测试用例的数量。每个测试用例的第一行包括两个整数 **N** 和 **Q**；随后一行包含 **Q** 个整数，代表商序列。

对于每个测试用例，输出与给定商序列相匹配的整数对数量。

- $1 \le T \le 10^5$ - $1 \le N \le 10^6$ - $1 \le Q \le 10$ **本翻译由 AI 自动生成**