n=int(input())
i,year,f=0,0,0
while i<n:
    year = int(input())
    f=(15+year+(year//4)-(year//100)+(year//400))%7
    if f == 1:
        print("9")
    if f == 2 or f == 0:
        print("6")
    if f == 3 or f == 4 or f == 5 or f == 6:
        print("5")
    i = i+1