func main() {
	//Enter your code here. Read input from STDIN. Print output to STDOUT
	var T, N, M, p1, p2 int
	io := bufio.NewReader(os.Stdin)
	fmt.Fscan(io, &T)
	for T > 0 {
		adjm := initialize(100, 6)
		fmt.Fscan(io, &N)
		for i := 0; i < N; i++ {
			fmt.Fscan(io, &p1, &p2)
			adjm[p1-1][p2-1] = 0
		}
		fmt.Fscan(io, &M)
		for i := 0; i < M; i++ {
			fmt.Fscan(io, &p1, &p2)
			adjm[p1-1][p2-1] = 0
			for j := 1; j <= 6; j++ {
				if (p1 - 1 + j) > 100-1 {
					break
				}
				adjm[p1-1][p1-1+j] = 101
			}
		}
		dist := floydWarshall(adjm, 100)
		if dist[0][99] == 101 {
			fmt.Println("-1")
		} else {
			fmt.Println(dist[0][99])
		}
		T--
	}
}

func (v Video) GetUserAnswer() int {
	var answer int
	stdin := bufio.NewReader(os.Stdin)
	fmt.Println("Title:", v.Title)
	fmt.Println("Description:", v.Description)

	fmt.Println("Available qualities: ")

	for i := 0; i < len(v.Links); i++ {
		fmt.Println(i+1, "Quality:", v.Links[i].Quality, "\tSize:", toMB(v.Links[i].Size), "MB")
	}

	fmt.Printf("Which quality do you want to donwload?")
	_, err := fmt.Fscan(stdin, &answer)
	stdin.ReadString('\n')

	if err != nil {
		fmt.Println(err)
		os.Exit(1)
	}

	for answer < 1 || answer > len(v.Links) {
		fmt.Printf("Invalid choice!")
		_, err := fmt.Fscan(stdin, &answer)
		stdin.ReadString('\n')

		if err != nil {
			fmt.Println(err)
			os.Exit(1)
		}
	}

	return answer
}

// DecodePolygon loads a polygon saved using EncodePolygon function.
func DecodePolygon(in io.Reader) (*polyclip.Polygon, error) {
	var ncontours int
	_, err := fmt.Fscan(in, &ncontours)
	if err != nil {
		return nil, err
	}
	polygon := polyclip.Polygon{}
	for i := 0; i < ncontours; i++ {
		var npoints, level int
		_, err = fmt.Fscan(in, &npoints, &level)
		if err != nil {
			return nil, err
		}
		c := polyclip.Contour{}
		for j := 0; j < npoints; j++ {
			p := polyclip.Point{}
			_, err = fmt.Fscan(in, &p.X, &p.Y)
			if err != nil {
				return nil, err
			}
			if j > 0 && p.Equals(c[len(c)-1]) {
				continue
			}
			if j == npoints-1 && p.Equals(c[0]) {
				continue
			}
			c.Add(p)
		}
		if len(c) < 3 {
			continue
		}
		polygon.Add(c)
	}
	return &polygon, nil
}

func reader() {
	file, err := os.Open("input.txt")
	if err != nil {
		panic(err)
	}
	defer file.Close()

	var scan struct {
		A, B float32
		C    bool
		D    string
	}

	log.Printf("scan: %v", scan)
	fmt.Fscan(file, &scan.A, &scan.B)
	log.Printf("scan: %v", scan)
	fmt.Fscan(file, &scan.C, &scan.D)
	log.Printf("scan: %v", scan)

	fmt.Fscanln(file, &scan.A, &scan.B, &scan.C, &scan.D)
	log.Printf("scan: %v", scan)

	fmt.Fscanf(file, "The Green %s %f %t %f", &scan.D, &scan.B, &scan.C, &scan.A)
	log.Printf("scan: %v", scan)
}

func init() {
	merkkiRuuduksi := map[rune]Ruutu{
		'#': Seinä,
		'.': Tyhjä,
		'o': Kivi,
		'x': Kuoppa,
		'p': Pelaaja,
		'm': Maali,
	}

	file, err := os.Open("testitaso.mp")
	if err != nil {
		panic("En saanut ladattua tasoa: " + err.Error())
	}

	fmt.Fscan(file, &kartanLeveys, &kartanKorkeus, &PelaajaX, &PelaajaY)

	kartta = make([]Ruutu, kartanLeveys*kartanKorkeus)
	for y := 0; y < kartanKorkeus; y++ {
		var rivi string
		fmt.Fscan(file, &rivi)
		for x, merkki := range rivi {
			LaitaKartanKohtaan(x, y, merkkiRuuduksi[merkki])
		}
	}
}

func (self *node) constructKeys(file *os.File, keyCnt int, typ int) {
	var key common.CellValue
	var intval common.IntVal
	var fltval common.FltVal
	var strval common.StrVal
	for i := 0; i < keyCnt; i++ {
		switch typ {
		case common.IntCol:
			fmt.Fscan(file, &intval)
			key = intval
		case common.FltCol:
			fmt.Fscan(file, &fltval)
			key = fltval
		case common.StrCol:
			fmt.Fscan(file, &strval)
			key = strval
		}
		self.keys = append(self.keys, key)
	}
	var recordId int64
	if self.isLeaf() {
		for i := 0; i < keyCnt; i++ {
			fmt.Fscan(file, &recordId)
			self.recordIds = append(self.recordIds, recordId)
		}
	}
}

func grade(in io.Reader) []byte {
	var n, m int
	fmt.Fscanln(in, &n, &m)

	records := []record{}

	var overallavg float64
	for i := 0; i < n; i++ {
		r := record{}
		fmt.Fscan(in, &r.name)
		for j := 0; j < m; j++ {
			var tmp float64
			fmt.Fscan(in, &tmp)
			r.grades = append(r.grades, tmp)
			r.avg += tmp
		}
		r.avg /= float64(len(r.grades))
		overallavg += r.avg
		records = append(records, r)
	}
	overallavg /= float64(n)

	o := new(bytes.Buffer)
	fmt.Fprintf(o, "%.2f\n", overallavg)
	for _, r := range records {
		fmt.Fprintf(o, "%s %.2f\n", r.name, r.avg)
	}
	return o.Bytes()
}

func main() {
	h := &IntHeap{}
	heap.Init(h)
	dict := map[int]bool{}
	var inputSize int
	var diff int
	io := bufio.NewReader(os.Stdin)

	fmt.Fscan(io, &inputSize)
	fmt.Fscan(io, &diff)
	for i := 0; i < inputSize; i++ {
		var number int
		fmt.Fscan(io, &number)
		heap.Push(h, number)
		dict[number] = true
	}
	pairCount := 0
	for i := 0; h.Len() > 0; i++ {
		curr := heap.Pop(h).(int)
		_, ok := dict[curr+diff]
		if ok {
			pairCount++
		}
	}
	fmt.Println(pairCount)
}

func main() {
	bi := bufio.NewReader(os.Stdin)
	bo := bufio.NewWriter(os.Stdout)
	defer bo.Flush()

	var n, m int
	fmt.Fscanln(bi, &n, &m)

	g := make([]int, n)
	for i := range g {
		fmt.Fscan(bi, &g[i])
	}

	b := make([]int, m)
	for i := range b {
		fmt.Fscan(bi, &b[i])
	}

	sort.Ints(g)
	sort.Ints(b)

	res := sum(g) // no one takes

	for k := 1; k <= min(len(b), len(g)); k++ {
		new_res := sum(g[:len(g)-k]) + sum(b[:len(b)-k])*k
		if new_res < res {
			res = new_res
		}
	}

	fmt.Fprintln(bo, res)
}

func main() {
	var inputSize int
	io := bufio.NewReader(os.Stdin)
	fmt.Fscan(io, &inputSize)
	var maxDiff int
	var firstStr string
	var secondStr string

	for i := 0; i < inputSize; i++ {
		fmt.Fscan(io, &maxDiff)
		fmt.Fscan(io, &firstStr)
		fmt.Fscan(io, &secondStr)
		best := 0
		for j := 0; j < len(firstStr); j++ {
			best1 := getBest(firstStr, secondStr, 0, j, maxDiff)
			best2 := getBest(firstStr, secondStr, j, 0, maxDiff)
			if best1 > best && best1 >= best2 {
				best = best1
			}
			if best2 > best && best2 >= best1 {
				best = best2
			}
		}
		fmt.Println(best)
	}

}

func (s *Sudoku) readCages(f *os.File) error {
	var ncages int
	fmt.Fscan(f, &ncages)

	s.Cages = make([]*Cage, ncages)

	for i := 0; i < ncages; i++ {
		var sum int8
		var ncells int
		fmt.Fscan(f, &sum, &ncells)

		cage := &Cage{
			Sum:   sum,
			Cells: make([]*Cell, ncells),
		}

		var row, col int8
		for j := 0; j < ncells; j++ {
			fmt.Fscanf(f, "%d,%d", &col, &row)
			cage.Cells[j] = &Cell{
				Row: row,
				Col: col,
			}
		}

		s.Cages[i] = cage
	}

	return nil
}

func main() {
	var userURL string
	stdin := bufio.NewReader(os.Stdin)

	fmt.Println("Enter a valid URL:")
	_, err := fmt.Fscan(stdin, &userURL)
	stdin.ReadString('\n')

	if err != nil {
		fmt.Println(err)
		os.Exit(1)
	}

	for len(userURL) == 0 {
		fmt.Println("[!] URL can't be empty!")
		_, err := fmt.Fscan(stdin, &userURL)
		stdin.ReadString('\n')
		if err != nil {
			fmt.Println(err)
			os.Exit(1)
		}
	}

	response := url.GetPageSource(userURL)
	videoUser := url.GetVideoDetails(response)
	videoNumber := videoUser.GetUserAnswer()
	url.DownloadFile(videoUser.Links[videoNumber-1].Type, videoUser)
}

func getEventId(sysCall string) uint32 {
	f, err := os.Open(TracePath + EventPath + "/" + sysCall + "/format")
	if err != nil {
		log.Fatal(err)
	}
	defer f.Close()
	var token string
	for {
		_, err = fmt.Fscan(f, &token)
		if err != nil {
			log.Fatal(err)
		}
		if token == "ID:" {
			_, err = fmt.Fscan(f, &token)
			if err != nil {
				log.Fatal(err)
			}
			v, err := strconv.Atoi(token)
			if err != nil {
				log.Fatal(err)
			}
			return uint32(v)
		}
	}
}

func load(stdin io.Reader) {
	var t int
	fmt.Fscan(stdin, &t)
	for i := 0; i < t; i++ {
		var n, c, m int
		fmt.Fscan(stdin, &n, &c, &m)
		fmt.Println(solve(n, c, m))
	}
}

func load(stdin io.Reader) {
	var t int
	fmt.Fscan(stdin, &t)
	for i := 0; i < t; i++ {
		var a, b int
		fmt.Fscan(stdin, &a, &b)
		fmt.Println(a + b)
	}
}

func load(stdin io.Reader) {
	var n int
	fmt.Fscan(stdin, &n)
	A := make([]int, n)
	for i := 0; i < len(A); i++ {
		fmt.Fscan(stdin, &A[i])
	}
	solve(A)
}

// train builds a markov chain table from the text in r.
func train(r io.Reader) map[prefix][]string {
	states := make(map[prefix][]string)
	pref := emptyPrefix()
	var w string
	for n, _ := fmt.Fscan(r, &w); n > 0; n, _ = fmt.Fscan(r, &w) {
		addSuffix(states, pref, w)
		pref = newPrefix(append(pref[1:], w)...)
	}
	addSuffix(states, pref, NONWORD)
	return states
}

func solve(r io.Reader, w io.Writer) {

	var n int
	fmt.Fscan(r, &n)

	for i := 0; i < n; i++ {
		var s string
		fmt.Fscan(r, &s)
		fmt.Fprintf(w, "%d\n", uniqDashC(s))
	}
}

/**
Problem: https://www.hackerrank.com/challenges/coin-change
*/
func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, m int
	fmt.Fscan(reader, &n)
	fmt.Fscan(reader, &m)
	var c []int = make([]int, m)
	for i := range c {
		fmt.Fscan(reader, &c[i])
	}

	fmt.Println(CoinChange(n, c))
}

// DecodeConfigPNM reads and returns header data of PNM files.
//
// This may be useful to obtain the actual file type and for files that have a
// Maxval other than the maximum supported Maxval. To apply gamma correction
// this value is needed. Note that gamma correction is not performed by the
// decoder.
func DecodeConfigPNM(r *bufio.Reader) (c PNMConfig, err error) {
	// PNM magic number
	if _, err = fmt.Fscan(r, &c.magic); err != nil {
		return
	}
	switch c.magic {
	case "P1", "P2", "P3", "P4", "P5", "P6":
	case "P7":
		return c, errors.New("pnm: reading PAM images is not supported (yet).")
	default:
		return c, errors.New("pnm: invalid format " + c.magic[0:2])
	}

	// Image width
	if err = skipComments(r, false); err != nil {
		return
	}
	if _, err = fmt.Fscan(r, &c.Width); err != nil {
		return c, errors.New("pnm: could not read image width, " + err.Error())
	}
	// Image height
	if err = skipComments(r, false); err != nil {
		return
	}
	if _, err = fmt.Fscan(r, &c.Height); err != nil {
		return c, errors.New("pnm: could not read image height, " + err.Error())
	}
	// Number of colors, only for gray and color images.
	// For black and white images this is 2, obviously.
	if c.magic == "P1" || c.magic == "P4" {
		c.Maxval = 2
	} else {
		if err = skipComments(r, false); err != nil {
			return
		}
		if _, err = fmt.Fscan(r, &c.Maxval); err != nil {
			return c, errors.New("pnm: could not read number of colors, " + err.Error())
		}
	}

	if c.Maxval > 65535 || c.Maxval <= 0 {
		err = fmt.Errorf("pnm: maximum depth is 16 bit (65,535) colors but %d colors found", c.Maxval)
		return
	}

	// Skip comments after header.
	if err = skipComments(r, true); err != nil {
		return
	}

	return c, nil
}