write a go solution for F1. Shohag Loves Counting (Easy Version)time limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis is the easy version of the problem. The only differences between the two versions of this problem are the constraints on t, m, and the sum of m. You can only make hacks if both versions of the problem are solved.For an integer array a of length n, define f(k) as the greatest common divisor (GCD) of the maximum values of all subarrays^∗ of length k. For example, if the array is [2,1,4,6,2], then f(3)=operatornamegcd(operatornamemax([2,1,4]),operatornamemax([1,4,6]),operatornamemax([4,6,2]))=operatornamegcd(4,6,6)=2.An array is good if f(i)neqf(j) is satisfied over all pairs 1<=iltj<=n.Shohag has an integer m. Help him count the number, modulo 998,244,353, of non-empty good arrays of arbitrary length such that each element of the array is an integer from 1 to m.^∗An array d is a subarray of an array c if d can be obtained from c by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.InputThe first line contains a single integer t (1<=t<=10^4) — the number of test cases.The first and only line of each test case contains an integer m (1<=m<=10^5).It is guaranteed that the sum of m over all test cases does not exceed 10^5.OutputFor each test case, output an integer — the number of valid arrays modulo 998,244,353.ExampleInput3259Output4
29
165
NoteIn the first test case, the valid arrays are [1], [1,2], [2], and [2,1].In the second test case, there are a total of 29 valid arrays. In particular, the array [2,1,4] with length n=3 is valid because all elements are from 1 to m=5 and f(1), f(2) and f(n=3) all are distinct:  f(1)=operatornamegcd(operatornamemax([2]),operatornamemax([1]),operatornamemax([4]))=operatornamegcd(2,1,4)=1.  f(2)=operatornamegcd(operatornamemax([2,1]),operatornamemax([1,4]))=operatornamegcd(2,4)=2.  f(3)=operatornamegcd(operatornamemax([2,1,4]))=operatornamegcd(4)=4.. Output only the code with no comments, explanation, or additional text.