Given an integer n, you have to find:

$$lcm(1, 2, 3, \dots, n)$$

lcm means least common multiple. For example lcm(2, 5, 4) = 20, lcm(3, 9) = 9, lcm(6, 8, 12) = 24.

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing an integer n (2 ≤ n ≤ 10⁸).

For each case, print the case number and lcm(1, 2, 3, ..., n). As the result can be very big, print the result modulo 2³².