people are wandering in the city from second to the -th second. They are numbered from to . The city can be viewed as a grid, and the top left square is .

The -th person is standing at square at first. For each second, every person will move to an adjacent square. Two squares are adjacent if and only if they share a common edge. In each -th second (), the -th person's move can be described as a character .

Let be the current square of this person in the -th second, and be the position where he/she will appear in the -th second, then:

Define as the number of different pairs such that and person and are in the same square in the -th second.

In order to know how many pairs of these people will meet in the -th second, you need to calculate the value .

It is guaranteed that every person's location in every second is legal. Formally speaking, let be the -th person's location, then always satisfied.