You play a computer game. In this game, you lead a party of m heroes, and you have to clear a dungeon with n monsters. Each monster is characterized by its power a_i. Each hero is characterized by his power p_i and endurance s_i.

The heroes clear the dungeon day by day. In the beginning of each day, you choose a hero (exactly one) who is going to enter the dungeon this day.

When the hero enters the dungeon, he is challenged by the first monster which was not defeated during the previous days (so, if the heroes have already defeated k monsters, the hero fights with the monster k + 1). When the hero fights the monster, there are two possible outcomes:

  * if the monster's power is strictly greater than the hero's power, the hero retreats from the dungeon. The current day ends; 
  * otherwise, the monster is defeated. 



After defeating a monster, the hero either continues fighting with the next monster or leaves the dungeon. He leaves the dungeon either if he has already defeated the number of monsters equal to his endurance during this day (so, the i-th hero cannot defeat more than s_i monsters during each day), or if all monsters are defeated — otherwise, he fights with the next monster. When the hero leaves the dungeon, the current day ends.

Your goal is to defeat the last monster. What is the minimum number of days that you need to achieve your goal? Each day you have to use exactly one hero; it is possible that some heroes don't fight the monsters at all. Each hero can be used arbitrary number of times.

Input

The first line contains one integer t (1 ≤ t ≤ 10^5) — the number of test cases. Then the test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of monsters in the dungeon.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9), where a_i is the power of the i-th monster.

The third line contains one integer m (1 ≤ m ≤ 2 ⋅ 10^5) — the number of heroes in your party.

Then m lines follow, each describing a hero. Each line contains two integers p_i and s_i (1 ≤ p_i ≤ 10^9, 1 ≤ s_i ≤ n) — the power and the endurance of the i-th hero.

It is guaranteed that the sum of n + m over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case print one integer — the minimum number of days you have to spend to defeat all of the monsters (or -1 if it is impossible).

Example

Input


2
6
2 3 11 14 1 8
2
3 2
100 1
5
3 5 100 2 3
2
30 5
90 1


Output


5
-1
import java.io.*; 
import java.math.*;
import java.util.*;
import java.awt.Point;
 
public class Main {
	static final long MOD = 998244353L;
	static final long INF = 100000000000007L;
	//static final long MOD = 1000000007L;
	//static final int INF = 1000000007;
	
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int Q = sc.ni();
		StringBuilder ans = new StringBuilder();
		for (int q = 0; q < Q; q++) {
			int N = sc.ni();
			int[] monsters = new int[N];
			int toughest = 0;
			for (int i = 0; i < N; i++) {
				monsters[i] = sc.ni();
				toughest = Math.max(toughest,monsters[i]);
			}
			int M = sc.ni();
			int[][] heroesT = new int[M][2];
			for (int i = 0; i < M; i++) {
				heroesT[i][0] = sc.ni(); //power
				heroesT[i][1] = sc.ni(); //endurance
			}
			heroesT = sort(heroesT);
			int[] heroes = new int[N+1];
			int maxPow = 0;
			for (int i = M-1; i >= 0; i--) {
				if (heroesT[i][0] > maxPow) {
					heroes[heroesT[i][1]] = heroesT[i][0];
					maxPow = heroesT[i][0];
				}
			}
			int V = 0;
			boolean impossible = true;
			for (int i = 1; i <= N; i++) {
				if (heroes[i] > 0) {
					V++;
				}
				if (heroes[i] >= toughest) {
					impossible = false;
				}
			}
			if (impossible) {
				ans.append("-1\n");
				continue;
			}
			
			int[][] nums = new int[V][2];
			int index = 0;
			for (int i = 1; i <= N; i++) {
				if (heroes[i] > 0) {
					nums[index][0] = heroes[i]; //power
					nums[index][1] = i; //endurance
					index++;
				}
			}
			
			int pos = 0;
			int days = 0;
			while (pos < N) {
				int kills = 0;
				int tough = monsters[pos];
				while (true) {
					int low = 0;
					int high = V-1;
					while (low < high) {
						int mid = (low+high+1)/2;
						if (nums[mid][0] >= tough) {
							low = mid;
						} else {
							high = mid-1;
						}
					}
					int endur = nums[low][1];
					if (kills < endur) {
						kills++;
						pos++;
						if (pos == N) break;
						tough = Math.max(tough,monsters[pos]);
					} else {
						break;
					}
				}
				days++;
			}
			ans.append(days + "\n");
		}
		System.out.print(ans);
 	}
	
	static class SegmentTree {
	    private Node[] heap;
	    public long[] array;
	    public int size;

	    /**
	     * Time-Complexity:  O(n*log(n))
	     *
	     * @param array the Initialization array
	     */
	    public SegmentTree(long[] array) {
	        this.array = Arrays.copyOf(array, array.length);
	        //The max size of this array is about 2 * 2 ^ log2(n) + 1
	        size = (int) (2 * Math.pow(2.0, Math.floor((Math.log((double) array.length) / Math.log(2.0)) + 1)));
	        heap = new Node[size];
	        build(1, 0, array.length);
	    }

	    //Initialize the Nodes of the Segment tree
	    private void build(int v, int from, int size) {
	        heap[v] = new Node();
	        heap[v].from = from;
	        heap[v].to = from + size - 1;

	        if (size == 1) {
	            heap[v].sum = array[from];
	            heap[v].min = array[from];
	        } else {
	            //Build childs
	            build(2 * v, from, size / 2);
	            build(2 * v + 1, from + size / 2, size - size / 2);

	            heap[v].sum = heap[2 * v].sum + heap[2 * v + 1].sum;
	            //min = min of the children
	            heap[v].min = Math.min(heap[2 * v].min, heap[2 * v + 1].min);
	        }
	    }

	    /**
	     * Range Sum Query
	     *
	     * Time-Complexity: O(log(n))
	     *
	     * @param  from from index
	     * @param  to to index
	     * @return sum
	     */
	    public long rsq(int from, int to) {
	        return rsq(1, from, to);
	    }

	    private long rsq(int v, int from, int to) {
	        Node n = heap[v];

	        //If you did a range update that contained this node, you can infer the Sum without going down the tree
	        if (n.pendingVal != null && contains(n.from, n.to, from, to)) {
	            return (to - from + 1) * n.pendingVal;
	        }

	        if (contains(from, to, n.from, n.to)) {
	            return heap[v].sum;
	        }

	        if (intersects(from, to, n.from, n.to)) {
	            propagate(v);
	            long leftSum = rsq(2 * v, from, to);
	            long rightSum = rsq(2 * v + 1, from, to);

	            return leftSum + rightSum;
	        }

	        return 0;
	    }

	    /**
	     * Range Min Query
	     * 
	     * Time-Complexity: O(log(n))
	     *
	     * @param  from from index
	     * @param  to to index
	     * @return min
	     */
	    public long rMinQ(int from, int to) {
	        return rMinQ(1, from, to);
	    }

	    private long rMinQ(int v, int from, int to) {
	        Node n = heap[v];


	        //If you did a range update that contained this node, you can infer the Min value without going down the tree
	        if (n.pendingVal != null && contains(n.from, n.to, from, to)) {
	            return n.pendingVal;
	        }

	        if (contains(from, to, n.from, n.to)) {
	            return heap[v].min;
	        }

	        if (intersects(from, to, n.from, n.to)) {
	            propagate(v);
	            long leftMin = rMinQ(2 * v, from, to);
	            long rightMin = rMinQ(2 * v + 1, from, to);

	            return Math.min(leftMin, rightMin);
	        }

	        return Long.MAX_VALUE;
	    }


	    /**
	     * Range Update Operation.
	     * With this operation you can update either one position or a range of positions with a given number.
	     * The update operations will update the less it can to update the whole range (Lazy Propagation).
	     * The values will be propagated lazily from top to bottom of the segment tree.
	     * This behavior is really useful for updates on portions of the array
	     * <p>
	     * Time-Complexity: O(log(n))
	     *
	     * @param from  from index
	     * @param to    to index
	     * @param value value
	     */
	    public void update(int from, int to, long value) {
	        update(1, from, to, value);
	    }

	    private void update(int v, int from, int to, long value) {

	        //The Node of the heap tree represents a range of the array with bounds: [n.from, n.to]
	        Node n = heap[v];

	        /**
	         * If the updating-range contains the portion of the current Node  We lazily update it.
	         * This means We do NOT update each position of the vector, but update only some temporal
	         * values into the Node; such values into the Node will be propagated down to its children only when they need to.
	         */
	        if (contains(from, to, n.from, n.to)) {
	            change(n, value);
	        }

	        if (n.size() == 1) return;

	        if (intersects(from, to, n.from, n.to)) {
	            /**
	             * Before keeping going down to the tree We need to propagate the
	             * the values that have been temporally/lazily saved into this Node to its children
	             * So that when We visit them the values  are properly updated
	             */
	            propagate(v);

	            update(2 * v, from, to, value);
	            update(2 * v + 1, from, to, value);

	            n.sum = heap[2 * v].sum + heap[2 * v + 1].sum;
	            n.min = Math.min(heap[2 * v].min, heap[2 * v + 1].min);
	        }
	    }

	    //Propagate temporal values to children
	    private void propagate(int v) {
	        Node n = heap[v];

	        if (n.pendingVal != null) {
	            change(heap[2 * v], n.pendingVal);
	            change(heap[2 * v + 1], n.pendingVal);
	            n.pendingVal = null; //unset the pending propagation value
	        }
	    }

	    //Save the temporal values that will be propagated lazily
	    private void change(Node n, long value) {
	        n.pendingVal = value;
	        n.sum = n.size() * value;
	        n.min = value;
	        array[n.from] = value;

	    }

	    //Test if the range1 contains range2
	    private boolean contains(int from1, int to1, int from2, int to2) {
	        return from2 >= from1 && to2 <= to1;
	    }

	    //check inclusive intersection, test if range1[from1, to1] intersects range2[from2, to2]
	    private boolean intersects(int from1, int to1, int from2, int to2) {
	        return from1 <= from2 && to1 >= from2   //  (.[..)..] or (.[...]..)
	                || from1 >= from2 && from1 <= to2; // [.(..]..) or [..(..)..
	    }

	    //The Node class represents a partition range of the array.
	    static class Node {
	        long sum;
	        long min;
	        //Here We store the value that will be propagated lazily
	        Long pendingVal = null;
	        int from;
	        int to;

	        int size() {
	            return to - from + 1;
	        }

	    }
	}
	
	static class DisjointSetUnion {
		public int[] parent;
		public int[] weight;
		public int count;

		public DisjointSetUnion(int nodes) {
			count = nodes;
			parent = new int[nodes];
			weight = new int[nodes];
			for (int i = 0; i < nodes; i++) {
				parent[i] = i;
				weight[i] = 1;
			}
		}
		//"find"
		public int root(int p) {
			while (p != parent[p]) {
				p = parent[p];
			}
			return p;
		}

		//"union"
		public void connect(int p, int q) {
			int rootP = root(p);
			int rootQ = root(q);
			if (rootP == rootQ) return;
			if (weight[rootP] < weight[rootQ]) {
				parent[rootP] = rootQ;
				weight[rootQ] += weight[rootP];
			} else {
				parent[rootQ] = rootP;
				weight[rootP] += weight[rootQ];
			}
			count--;
		}

		public boolean connected(int p, int q) {
			return root(p) == root(q);
		}
	}
    
    public static long power(long x, long y, long p) { 
        // Initialize result
        long res = 1;
         
        // Update x if it is more   
        // than or equal to p 
        x = x % p;  
      
        while (y > 0) 
        { 
            // If y is odd, multiply x 
            // with result 
            if((y & 1)==1) 
                res = (res * x) % p; 
      
            // y must be even now 
            // y = y / 2 
            y = y >> 1;  
            x = (x * x) % p;  
        } 
        return res; 
    }
    
    public static long dist(int[] point, int[] point2) {
    	return (long)(Math.pow((point2[1]-point[1]),2)+Math.pow((point2[0]-point[0]),2));
    }
    
    public static long gcd(long a, long b) {
    	if (b == 0)
    		return a;
    	else
    		return gcd(b,a%b);
    }
    
    public static int[][] sort(int[][] array) {
    	//Sort an array (immune to quicksort TLE)
		Random rgen = new Random();
		for (int i = 0; i < array.length; i++) {
		    int randomPosition = rgen.nextInt(array.length);
		    int[] temp = array[i];
		    array[i] = array[randomPosition];
		    array[randomPosition] = temp;
		}
		Arrays.sort(array, new Comparator<int[]>() {
			  @Override
        	  public int compare(int[] arr1, int[] arr2) {
				  return arr1[1]-arr2[1]; //ascending order
	          }
		});
		return array;
	}
    
    public static long[][] sort(long[][] array) {
    	//Sort an array (immune to quicksort TLE)
		Random rgen = new Random();
		for (int i = 0; i < array.length; i++) {
		    int randomPosition = rgen.nextInt(array.length);
		    long[] temp = array[i];
		    array[i] = array[randomPosition];
		    array[randomPosition] = temp;
		}
		Arrays.sort(array, new Comparator<long[]>() {
			  @Override
			  //Ascending order
        	  public int compare(long[] arr1, long[] arr2) {
				  if (arr1[1] < arr2[1])
					  return -1;
				  if (arr1[1] > arr2[1])
					  return 1;
				  return 0;
	          }
		});
		return array;
	}
    
    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int ni() { 
            return Integer.parseInt(next()); 
        } 
  
        long nl() { 
            return Long.parseLong(next()); 
        } 
  
        double nd() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() { 
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str; 
        }
    }
}