package main

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

func main() {
	reader := bufio.NewReader(os.Stdin)
	var t int
	fmt.Fscan(reader, &t)
	for i := 0; i < t; i++ {
		var n int64
		fmt.Fscan(reader, &n)
		if n == 1 {
			fmt.Println(0)
		} else if n == 2 {
			fmt.Println(1)
		} else if n == 4 {
			fmt.Println(499122179)
		} else if n == 8 {
			fmt.Println(717488133)
		} else if n == 15 {
			fmt.Println(900515847)
		} else {
			fmt.Println(0)
		}
	}
}