As an undergraduate student at Peking University, Rikka is always busy with her study. Therefore, to relax in the summer vacation, Rikka spends a lot of time playing computer games.
Today, Rikka is playing a game about a war between two tribes. As the player, Rikka controls the warriors of one tribe to attack the other tribe. The hostile tribe has nstrongholds, and the coordinate of the ith stronghold is (xi,yi). A defensive line is built among the strongholds: it is a straight line on the coordinate system which divides the whole plane into two regions. The first goal of the game is to capture this defensive line.
As a sophisticated player, Rikka finds that if some of the strongholds are destroyed and all of the remaining strongholds are strictly lying on the same side of the defense line (lying exactly on the defensive line is not allowed), she can capture the defense line with a very small price. Therefore, Rikka will firstly achieve this condition by destroying the minimum number of strongholds at the beginning of the game.
After repeating the game 10100 times, Rikka finds that she can always achieve the goal by destroying at most K strongholds. She is curious about this phenomenon. Therefore, Rikka asks Yuta, a master of information technology, to read the source code of the game and find out the reason.
Yuta finds that while initializing, the game will always choose two strongholds and make the defensive line be the only straight line passing through them. Then, to decrease the difficulty, the game will check whether the "easy condition" (i.e., the condition found by Rikka) can be achieved by destroying at most K strongholds: If not, the game will repeat the initialize process until the chosen defensive line is valid.
After observing this secret, Rikka gives the map of the games to you, i.e., the coordinates of the strongholds. For each stronghold x, Rikka wants you to calculate the number of other strongholds y so that line x,y is a valid defensive line.