Migrated from Lutece 762 铁路

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

很久很久以前，E国遭遇了一次巨大的冲击。E国的铁路运输网已经完全崩溃。但是伟大的列车托夫出现了，他领导着E国人重新开始修铁路。为了生产资料的运输，我们希望任意的两个城市都能够经由铁路直接或间接连通。

但是E国的城市修建的十分奇异，以至于每个城市至多只能和其它城市中的$k$座之间直接修建一条铁路。现在，E国有$n$个城市，那么最多能在E国建设多少条铁路？这里，认为在两个城市间直接铺设多条铁路是不合法的。如果无论怎么修建都不能连通所有城市，则输出$0$。

Input

输入包含多组测试数据。第一行是一个整数$T$ ($T\leq 1000$)，表示测试组数。随后有$T$行，每行有两个整数$n$, $k$($1\leq n\leq 10000, 0\leq k\leq 10000$)分别表示，E国城市的数目和每个城市最多能直接相连的城市个数。

Output

对于每组输入数据，输出包含所求数目的一行。

Samples

2
5 3
5 0

7
0

Resources

第五届ACM趣味程序设计竞赛第三场（正式赛）