for t in range(int(input())): n = int(input()) ans = ((1<