SP9694 QB - Quelling Blade

Mr. Sheep lost himself in a computer game. In this game, he plays the part of a super hero and fight with the evil. The equipment is very important in this game and Mr. Sheep thinks the Quelling Blade is the most powerful weapon. In this game, each type of weapon costs hero some money, and brings the hero benefits. If the hero buys two weapons (no matter they have the same type or not), the benefit values are accumulated. That is to say, if the hero buys two weapons with benefit 3 and 5, the hero will get total benefit value 8=3+5. There are some requirements for each weapon. If the hero wants to buy a certain weapon, he may need some other weapons first. For example, if hero wants to buy a _Divine Rapier_, he needs a _Demon Edge_ and a _Scared Relic_. Of course, if he wants to buy the second _Devine Rapier_, he must buy another _Demon Edge_ and another _Scared Relic_ first. Notice that the existing weapon will not disappear after the trade. Note that a weapon may need multiple weapons with same type. And you may assume that a type of weapon is required by at most one other type of weapon. The hero is busy with combat and has no time to earn money. Fortunately, the game will give the hero 1 coin per second. So if the hero wants to buy a _Quelling Blade_, the minimum total time for him to achieve his goal can be easily calculated. Mr. Sheep is a perfectionist. He not only wants to get the _Quelling Blade_ as soon as possible, but also wants to optimize every second during the game. He defines the utility of the game as the sum of the benefit value of the hero in each second. He calculates the utility from the start of the game until the second he gets _Quelling Blade_, exclusively. You may refer to the samples for further clarification. In the other words, you should define a way of process to buy the weapons for the hero, which minimize the total time to get _Quelling Blade_ and optimize the utility of the game.

There are hundreds of test cases, the number of test case are in the first line of the input. Notice that most of the test cases are relatively small. For each test case, the first line contains a single integer N denoting the number of different types of weapons. (1

For each test case, output a single integer denoting the optimal utility. You may assume that the answer fits into 64-bit signed integer.