package main

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

func numberSets(scanner *bufio.Scanner) []int64 {
	caseCnt := ReadInt(scanner)
	params := make([][]int64, caseCnt)
	var nMax int64
	for i := 0; i < caseCnt; i++ {
		params[i] = ReadInt64s(scanner)
		if params[i][1]-params[i][0]+1 > nMax {
			nMax = params[i][1] - params[i][0] + 1
		}
	}
	sieve := make([]bool, nMax+1)
	prime := make([]int64, 0)
	for i := int64(2); i <= nMax; i++ {
		if !sieve[i] {
			prime = append(prime, i)
			for j := i * i; j <= nMax; j += i {
				sieve[j] = true
			}
		}
	} // Find all prime numbers between 1 and nMax
	answer := make([]int64, caseCnt)
	for i := range params {
		println("Case", i+1) // Too slow
		A, B, P := params[i][0], params[i][1], params[i][2]
		uf := NewUF(B - A + 1)
		for _, p := range prime {
			if p < P {
				continue
			} else if p > B-A {
				break
			}
			beg := ((A + (p - 1)) / p) * p
			for n := beg; n <= B; n += p {
				uf.Union(beg-A, n-A)
			}
		}
		answer[i] = uf.Cnt
	}
	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 := large

	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)
	}
}