def main():
    t = int(input())
    for i in range(t):
        n = int(input())
        print([998244349, 4][n % 2])


if __name__ == '__main__':
    main()