给定正整数 $p$ 和 $n$。对于一个排列，我们称其中相邻两项产生「共振」当且仅当这两个数的和为 $p$ 的倍数。

请你构造一个 $1\sim n$ 的排列，最大化其中产生「共振」的次数。并输出该次数

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，代表数据的组数。

对于每组测试数据，输入包含一行，为由空格隔开的两个正整数 $n$ 和 $p$。

• 
  Subtask 0（15 pts）：$n\le 9$，$T\le 10$。
  


• 
  Subtask 1（10 pts）：$p=2$。
  


• 
  Subtask 2（30 pts）：$p=3$。
  


• 
  Subtask 3（45 pts）：无特殊限制。
  

对于所有数据，$1\le n\le 10^5$，$1\le p\le 10^8$，$1\le T\le 10^4$，$1\le \sum n\le 3\times 10^5$。

桶、贪心