该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小 L 正在尝试解决 CF 上的一道 2A。

题目描述

小 L 不会做，于是他给你一个整数 $n$，请你对于所有 $1 \leq i, j \leq n$，求出 $\lambda(\operatorname{lcm}(i, j))$ 的和，其中 $\lambda(n)$ 在 $n$ 的不去重质因数个数有偶数个时取 $1$，其他时候取 $-1$。

由于结果可能很大，你只需要求出结果对 $2^{32}$ 取模的值。

输入格式

本题有多组测试数据。

第一行，一个整数 $T$，表示数据组数；

对于每组数据：

一行，一个整数 $n$。

输出格式

对于每组数据，输出一行，一个整数，表示所求的值。

1
10

2

提示

对于 $10\%$ 的数据，$1 \leq n \leq 10^3$；

对于 $30\%$ 的数据，$1 \leq n \leq 10^6$；

对于 $50\%$ 的数据，$1 \leq n \leq 10^9$；

对于 $100\%$ 的数据，$1 \leq n \leq 10^{10}$，$1 \leq T \leq 10$。