Spiral Area Division

Time limit1sMemory limit64 MB

Summary

Given up to 100 points in an 80 by 80 square cut into 15 labeled pieces by alternating 3-to-1 splits, output the label containing each point.

Level: Easy3 of 10
Topics: Geometry, Simulation, Implementation
Solved: No attempts yet

Problem

An 80 by 80 square is repeatedly split into 3:1 area pieces by alternating vertical and horizontal cuts. The small piece receives labels 1 through 15. For each point $(x,y)$ not on a cut line, report its label.

Input

The first line contains $n$ points ( $1 \le n \le 100$ ). Each of the next $n$ lines contains $x$ and $y$ with $0 \le x,y \le 80$ .

Output

Print the region label for each point on its own line.

Examples1

Example 1

Input

Expected output