You’re designing a game console with a special board which can evaluate how balance people are. After the user stands on the board, it can record the movement of the user's "center of gravity".

Technically, the record is a sequence of n points on the 2D plane (the user's "center of gravity" projected to the game board), where the origin (0,0) is the center of the game board. Samples are taken every 0.01 second, so if the user stands on it for one minute, your database gets 6000 sample points.

In order to know better about his balancing status, the user can ask the game console some questions. Each question (i,j) means: count how many pairs of sample points, chosen from the interval between the i-th sample and the j-th sample (inclusive), whose Manhattan distance is no more than d, where d is the preset balance threshold parameter in the system.

Your task is to write a program that can answer the questions. Note that you don't have to answer the questions one by one. You can read all the questions first, and then answer them.