A141175.午枫的罗盘

午枫在宝箱中还发现了一个古老的罗盘。罗盘上刻着 $n$ 条刻度线 $l_0, l_1, \ldots, l_{n-1}$。

其中，$l_0$ 是任意一条起始刻度线。对于 $i > 0$，刻度线 $l_i$ 是由 $l_{i-1}$ 绕罗盘中心逆时针旋转 $\frac{180^\circ}{k}$ 得到的。

午枫注意到，当两条刻度线互相垂直时，它们会在航海定位中产生特殊的共鸣。他想知道：在所有 $n$ 条刻度线中，有多少对不同的刻度线 $(l_i, l_j)$（其中 $0 \le i < j < n$）是互相垂直的？

本题有多组测试数据。

输入第一行一个正整数 $T$（$1 \le T \le 10^5$），表示数据组数。

接下来 $T$ 行，每行两个正整数 $n, k$（$1 \le n, k \le 10^9$），含义同上。

对于每组数据，输出一行一个自然数，表示满足条件的刻度线对的数量。

数据范围

对于 $100\%$ 的数据，满足 $1 \le T \le 10^5$，$1 \le n, k \le 10^9$。