SP3461 SONG - Song Contest

每年，Cacophonea 大陆都会举办一场盛大的歌曲比赛，即 Cacophonean 歌曲大赛。大陆上的每个国家都会派出歌手或乐队参赛。所有 Cacophonea 的居民都可以为其他国家的表演投票，前提是不能投给自己国家的参赛节目。最终，每个国家会根据投票结果给 **r** 个节目打分：得到最多票数的节目将获得 **r** 分，第二多票数的节目获得 **r-1** 分，以此类推，票数排第 **r** 的节目获得 1 分，而其他得票较少的节目则无法得分。比赛的最终排名由各国累积的总分决定。 音乐制作人 Dustin 多年来一直关注这个比赛。最近，他发现一些国家的投票更像是出于政治而非艺术考虑： 1. 政治投票的国家倾向于选择邻国的节目。他们完全根据两个国家首都之间的欧几里得距离来判断受欢迎度，而不考虑节目本身的艺术质量。因此，首都距离最近的国家会获得最多票数，而距离最远的国家最少票数，甚至可能拿不到分（若 **r** < **s** - 1）。并不会出现两个或多个国家的首都距离同一个首都相同的情况。 2. 质量导向投票的国家则是基于每个节目的艺术质量进行评选，排名公正无争议。在这种情况下，各国的节目排名不会有并列。 Dustin 听说他可以通过节目中对政治投票国家给予特别关注来影响结果（如用他们的方言演唱或挥舞他们的国旗）。政治投票的国家得到更多关注，他们就会对该国节目产生更高的评价。然而，这种方式会降低节目原有的艺术质量，并可能显得俗套，这让质量导向的国家产生反感，从而对其进行惩罚。 具体而言，Dustin 可以把一个表演分为 **s** - 1 段。起初，这些段落全部代表表演者国家的原始艺术构思，但可以调整成如下形式： 1. 每一段献给某个政治投票国家，都会让该国家把表演者的国家排名提高一位（除非已经是第一位）。由于排名具唯一性，原来排名更高的国家将降低一位。 2. 质量投票国家对这种策略非常不满。因此，对每一段献给非本国的部分，质量导向国家会将表演者的国家排名降低一位（除非已经是最后一位）。 影响投票行为的只是献给不同国家的段落数，而不是表演的顺序。 Dustin 计划运用这些知识（其他制作人不知道的优势）就如何优化表演以获得最多的分数。你的任务是，计算出在最优策略下，这场表演能获得的最高总分数。

第一行输入一个整数 **n**，表示测试用例的数量。 接下来的每个测试用例中： - 第一行一个整数 **s** (1 < **s**

对于每个测试用例，输出一行一个整数，表示当最优利用表演调整策略后，一个节目在总得分中能获得的最大分数。 **本翻译由 AI 自动生成**