package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

func numberSets(scanner *bufio.Scanner) []int64 {
	caseCnt := ReadInt(scanner)
	answer := make([]int64, caseCnt)
	params := make([][]int64, caseCnt)
	for i := 0; i < caseCnt; i++ {
		params[i] = ReadInt64s(scanner)
	}
	for i := range params {
		A, B, P := params[i][0], params[i][1], params[i][2]
		n := B - A + 1
		uf := NewUF(n + 1)
		composite := make(map[int64]bool)
		sqrtN := int64(math.Sqrt(float64(n)))
		for j := int64(2); j <= sqrtN; j++ {
			if !composite[j] {
				for k := j; j*k <= n; k++ {
					composite[j*k] = true
					if j >= P || k >= P {
						uf.Union(j*k, j)
					} else {
						uf.Union(j, 2)
					}
				}
			}
		}
		answer[i] = uf.Cnt - 1
	}
	return answer
}

func main() {
	inputFiles := []string{"B-small-practice.in", "B-large-practice.in", "test.in"}
	outputFiles := []string{"result-small.out", "result-large.out", "test.out"}
	const (
		small = iota
		large
		test
	)

	fileType := test

	fin, _ := os.Open(inputFiles[fileType])
	defer fin.Close()

	scanner := bufio.NewScanner(fin)
	answer := numberSets(scanner)

	fout, _ := os.Create(outputFiles[fileType])
	defer fout.Close()

	for i, v := range answer {
		s := fmt.Sprintf("Case #%d: %d\n", i+1, v)
		fout.WriteString(s)
	}
}