B'Marin wants you to count number of permutations that are beautiful. A beautiful permutation of length n is a permutation that has the following property: gcd (1 cdot p_1, , 2 cdot p_2, , ... , , n cdot p_n) > 1, where gcd is the greatest common divisor. A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation ( 2 appears twice in the array) and [1,3, 4] is also not a permutation ( n=3 but there is 4 in the array). The first line contains one integer t ( 1 <= t <= 10^3 ) -- the number of test cases. Each test case consists of one line containing one integer n ( 1 <= n <= 10^3 ). For each test case, print one integer -- number of beautiful permutations. Because the answer can be very big, please print the answer modulo 998 ,244 ,353 . In first test case, we only have one permutation which is [1] but it is not beautiful because gcd(1 cdot 1) = 1 . In second test case, we only have one beautiful permutation which is [2, 1] because gcd(1 cdot 2, 2 cdot 1) = 2 . '...