Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Knight's Problem
 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 1684 Accepted: 302

Description

You must have heard of the Knight's Tour problem. In that problem, a knight is placed on an empty chess board and you are to determine whether it can visit each square on the board exactly once.

Let's consider a variation of the knight's tour problem. In this problem, a knight is place on an infinite plane and it's restricted to make certain moves. For example, it may be placed at (0, 0) and can make two kinds of moves: Denote its current place as (x,y), it can only move to (x+1,y+2) or (x+2,y+1). The goal of this problem is to make the knight reach a destination position as quickly as possible (i.e. make as less moves as possible).

Input

The first line contains an integer T ( T < 20) indicating the number of test cases.
Each test case begins with a line containing four integer: fx fy tx ty(-5000<=fx,fy,tx,ty<=5000). The knight is originally placed at (fx, fy) and (tx, ty) is its destination.

The following line contains an integer m(0 < m <= 10), indicating how many kinds of moves the knight can make.

Each of the following m lines contains two integer mx my(-10<=mx,my<=10; |mx|+|my|>0), which means that if a knight stands at (x,y), it can move to (x+mx,y+my).

Output

Output one line for each test case. It contains an integer indicating the least number of moves needed for the knight to reach its destination. Output "IMPOSSIBLE" if the knight may never gets to its target position.

Sample Input

2
0 0 6 6
5
1 2
2 1
2 2
1 3
3 1
0 0 5 5
2
1 2
2 1

Sample Output

3
IMPOSSIBLE

Source

[Submit]   [Go Back]   [Status]   [Discuss]