提示: 欢迎访问OurACM平台。
Problem 2205 据说题目很水

Accept: 256    Submit: 538
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Sunday最近对图论特别感兴趣,什么欧拉回路什么哈密顿回路,又是环又是树。在看完一本书后,他对自己特别有信心,便找到大牛牛犇犇,希望他出一题来考考自己。

在遥远的古代东方有N个城市,它们之间可以通过双向的道路相连。任意两个城市由不超过一条道路直接相连,而且没有城市的道路连向自身。但是牛犇犇是个纯情的小伙子,尽管他还没有女朋友,但他还是很讨厌第三者,以至于讨厌三这个数字。所以他希望Sunday能够构造一个N个城市的地图,这个地图中不能有任意三个城市能够相互直接到达,而且地图中的道路数目最多。

牛犇犇考虑到Sunday是个菜鸟,所以只让他回答上述地图含有的道路数目,而不需要输出地图是由哪些道路组成。(题外话:其实只是因为special judge的评测程序比较麻烦而已)

Input

第一行一个整数T(1 <= T <= 100),表示测试数据的组数。

每组数据只包含一个N(1 <= N <= 1000),表示N个城市。

Output

每组数据输出仅有一行,表示在符合题意下N个城市所能连接的最大道路数目。

Sample Input

2 3 4

Sample Output

2 4

Source

FOJ有奖月赛-2015年11月

Submit  Back  Status  Discuss