package main

import "fmt"

func main() {
	var n int
	fmt.Scanf("%d", &n)
	for i := 0; i < n; i++ {
		var x uint64
		fmt.Scanf("%d", &x)
		if isPrime(x) {
			fmt.Printf("%d 1\n", x)
		} else {
			fmt.Printf("%d 0\n", x)
		}
	}
}

func isPrime(x uint64) bool {
	if x < 2 {
		return false
	}
	if x < 4 {
		return true
	}
	if x%2 == 0 {
		return false
	}
	for i := uint64(3); i*i <= x; i += 2 {
		if x%i == 0 {
			return false
		}
	}
	return true
}