← 返回比赛

已结束 GESP巅峰赛#37

← 上一题下一题 →

A7502 | $午枫的罗盘$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

午枫在宝箱中还发现了一个古老的罗盘。罗盘上刻着 $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$），含义同上。

输出格式

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

输入输出样例

输入 #1

1
3 2

输出 #1

C++ 编辑器

输入

输出