import kotlin.math.min
import java.util.*
fun solve() {
val n = readLine()!!.toInt()
if (n % 3 == 0 || n % 5 == 0) {
println(0)
return
}
val t = n / 3
var i = 0
var ans = 100
while (i <= t) {
ans = min(ans, n - 3 * i - 5 * ((n - 3 * i) / 5))
i++
}
println(ans)
}
fun main() {
val t = readLine()!!.toInt()
repeat(t) { solve() }
}
aW1wb3J0IGtvdGxpbi5tYXRoLm1pbgppbXBvcnQgamF2YS51dGlsLioKCmZ1biBzb2x2ZSgpIHsKICAgIHZhbCBuID0gcmVhZExpbmUoKSEhLnRvSW50KCkKICAgIGlmIChuICUgMyA9PSAwIHx8IG4gJSA1ID09IDApIHsKICAgICAgICBwcmludGxuKDApCiAgICAgICAgcmV0dXJuCiAgICB9CiAgICB2YWwgdCA9IG4gLyAzCiAgICB2YXIgaSA9IDAKICAgIHZhciBhbnMgPSAxMDAKICAgIHdoaWxlIChpIDw9IHQpIHsKICAgICAgICBhbnMgPSBtaW4oYW5zLCBuIC0gMyAqIGkgLSA1ICogKChuIC0gMyAqIGkpIC8gNSkpCiAgICAgICAgaSsrCiAgICB9CiAgICBwcmludGxuKGFucykKfQoKZnVuIG1haW4oKSB7CiAgICB2YWwgdCA9IHJlYWRMaW5lKCkhIS50b0ludCgpCiAgICByZXBlYXQodCkgeyBzb2x2ZSgpIH0KfQoK