package main

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

const MOD = 999999893

func power(base, exp int64) int64 {
	res := int64(1)
	base %= MOD
	for exp > 0 {
		if exp%2 == 1 {
			res = (res * base) % MOD
		}
		base = (base * base) % MOD
		exp /= 2
	}
	return res
}

func modInverse(n int64) int64 {
	return power(n, MOD-2)
}

func parse(b []byte) int64 {
	res := int64(0)
	for _, c := range b {
		res = res*10 + int64(c-'0')
	}
	return res
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	if !scanner.Scan() {
		return
	}

	t := int(parse(scanner.Bytes()))

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for i := 0; i < t; i++ {
		scanner.Scan()
		n := parse(scanner.Bytes())

		m := n / 2
		x := power(2, m)
		x2 := (x * x) % MOD

		var num, den int64
		if n%2 == 0 {
			num = (2*x - 2) % MOD
			den = (4*x - x2 - 2) % MOD
		} else {
			num = (x - 1) % MOD
			den = (x2 + 2*x - 1) % MOD
		}

		num = (num%MOD + MOD) % MOD
		den = (den%MOD + MOD) % MOD

		ans := (num * modInverse(den)) % MOD
		fmt.Fprintln(out, ans)
	}
}