// DRAGONST
// Dragonstone
// Author: Constantine Sokol
// Complexity : O( ( N + Q ) * log N )
// Expected Verdict: AC
 
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
 
using namespace std;
 
const int logn = 19;
const int maxn = 200200;
 
struct point
{
	int x, y, id;
	point( int x = 0, int y = 0, int id = 0 ) : x( x ), y( y ), id( id ) {};
};
 
struct fenwick
{
	int limit, value[ maxn ], id[ maxn ];
	void init( int items )
	{
		limit = items + 10;
		for ( int i = 0; i < limit; i++ ) value[i] = 2000000002, id[i] = -1; 
	}
	void upd( int pos, int _value, int _id )
	{
		while ( pos < limit )
		{
			if ( value[ pos ] > _value )
			{
				value[ pos ] = _value;
				id[ pos ] = _id; 
			}
			pos = pos + pos - ( pos & ( pos - 1 ) );
		}
	}
	int query( int pos )
	{
		int _value = 2000000002, _id = -1;
		while ( pos )
		{
			if ( value[ pos ] < _value )
			{
				_value = value[ pos ];
				_id = id[ pos ];
			}
			pos = pos & ( pos - 1 );
		}
		return _id;
	}
};
 
int n, x[ maxn ], y[ maxn ], e = 0;
int yy[ maxn ], m;
fenwick fw;
point p[ maxn ];
pair< int, int > edges[ 8 * maxn ], weight_id[ 8 * maxn ];
int pr[ maxn ], f[ logn ][ maxn ], g[ logn ][ maxn ];
int tin[ maxn ], tout[ maxn ], timer = 0;
vector< int > graph[ maxn ]; 
 
void add_edge( int a, int b )
{
	edges[ e ] = make_pair( a, b );
	weight_id[ e ] = make_pair( max( x[a] - x[b], x[b] - x[a] ) + max( y[a] - y[b], y[b] - y[a] ), e );
	++e;
}    
 
bool cmp_x_y( point a, point b )
{
	return make_pair( a.x - a.y, a.y ) > make_pair( b.x - b.y, b.y );
}
 
bool cmp_y( point a, point b )
{
	return a.y > b.y;
}
 
int get_pos( int y )
{
	int l = 1, r = m - 1, result = 0;
	while ( l <= r )
	{
		int x = (l + r) / 2;
		if ( yy[x] >= y )
		{
			result = max( result, x );
			l = x + 1;
		} else r = x - 1;
	}
	return result + 1;
}
 
void process( point p[] )
{
	sort( p, p + n, cmp_y );
	int _last = (int)2e9; m = 0;
	for ( int i = 0; i < n; i++ )
	{
		if ( p[i].y == _last ) continue;
		yy[ m++ ] = p[i].y;
		_last = p[i].y;
	}
	fw.init( m );
	sort( p, p + n, cmp_x_y );
	for ( int i = 0; i < n; i++ )
	{
		int pos = get_pos( p[i].y );
		int closest_id = fw.query( pos );
		if ( closest_id != -1 ) add_edge( p[i].id, closest_id );
		fw.upd( pos, p[i].x + p[i].y, p[i].id );
	}
}
 
// -----------------------------------
 
bool cmp_edges( int a, int b )
{
	return max( x[a] - x[b], x[b] - x[a] ) + max( y[a] - y[b], y[b] - y[a] );
} 
 
int get_prev( int v )
{
	if ( pr[v] == v ) return v;
	pr[v] = get_prev( pr[v] );
	return pr[v];
} 
 
void dfs( int v, int prev )
{
	tin[v] = ++timer;
	for ( int i = 0; i < graph[v].size(); i++ )
	{
		int id = graph[v][i];
		int next = v ^ edges[id].first ^ edges[id].second;
		if ( next == prev ) continue;
		f[0][next] = v;
		g[0][next] = max( x[v] - x[next], x[next] - x[v] ) + max( y[v] - y[next], y[next] - y[v] );
		dfs( next, v );
	}
	tout[v] = timer;
}
 
int is_parent( int parent, int child )
{
	return ( tin[parent] <= tin[child] && tin[child] <= tout[parent] );
}
 
int lca( int a, int b )
{
	if ( is_parent( a, b ) ) return a;
	if ( is_parent( b, a ) ) return b;
	for ( int i = logn - 1; i >= 0; i-- )
		if ( !is_parent( f[i][a], b ) )
			a = f[i][a];
	return f[0][a];
}
 
int fun( int a, int b )
{
	if ( a == b ) return 0;
	int result = 0;
	for ( int i = logn - 1; i >= 0; i-- )
		if ( !is_parent( f[i][b], a ) )
		{
			result = max( result, g[i][b] );
			b = f[i][b];
		}
	result = max( result, g[0][b] );
	return result;
}
 
int query( int a, int b )
{
	int c = lca( a, b );
	return max( fun( c, a ), fun( c, b ) );
}
 
void solve_testcase()
{
	scanf("%d", &n); e = 0;
	for ( int i = 0; i < n; i++ ) scanf("%d%d", &x[i], &y[i]), pr[i] = i, graph[i].clear();
	// First
	for ( int i = 0; i < n; i++ ) p[i] = point( x[i], y[i], i ); 
	process( p );
	// Second
	for ( int i = 0; i < n; i++ ) p[i] = point( -x[i], y[i], i ); 
	process( p );
	// Third
	for ( int i = 0; i < n; i++ ) p[i] = point( x[i], -y[i], i );
	process( p );
	// Fourth
	for ( int i = 0; i < n; i++ ) p[i] = point( -x[i], -y[i], i ); 
	process( p );
	// Fifth
	for ( int i = 0; i < n; i++ ) p[i] = point( y[i], x[i], i ); 
	process( p );
	// Sixth
	for ( int i = 0; i < n; i++ ) p[i] = point( -y[i], x[i], i ); 
	process( p );
	// Seventh
	for ( int i = 0; i < n; i++ ) p[i] = point( y[i], -x[i], i );
	process( p );
	// Eighth
	for ( int i = 0; i < n; i++ ) p[i] = point( -y[i], -x[i], i ); 
	process( p );
	// --------------------------------------------------------
	sort( weight_id, weight_id + e );
	for ( int i = 0; i < e; i++ ) 
	{
		int a = edges[ weight_id[i].second ].first;
		int b = edges[ weight_id[i].second ].second;
		int pa = get_prev( a );
		int pb = get_prev( b );
		if ( pa == pb ) continue;
		pr[ pa ] = pb;
		graph[ a ].push_back( weight_id[i].second );
		graph[ b ].push_back( weight_id[i].second );    
	}
	f[0][0] = g[0][0] = 0; timer = 0;
	dfs( 0, -1 );
	// --------------------------------------------------------
	for ( int i = 1; i < logn; i++ )
		for ( int j = 0; j < n; j++ )
		{
			f[i][j] = f[i - 1][ f[i - 1][j] ];
			g[i][j] = max( g[i - 1][j], g[i - 1][ f[i - 1][j] ] );
		}
	int q; scanf("%d", &q);
	for ( int it = 0; it < q; it++ )
	{
		int a, b; scanf("%d%d", &a, &b); --a; --b;
		printf("%d\n", query( a, b ));
	} 
}
 
int main()
{
	int T; scanf("%d", &T);
	while ( T-- ) solve_testcase();
	return 0;
}