#1913. 「SFCOI-2」街舞

「SFCOI-2」街舞

题目背景

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

题目描述

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

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

输入格式

本题有多组测试数据。

第一行,一个整数 TT,表示数据组数;

对于每组数据:

一行,一个整数 nn

输出格式

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

1
10
2

提示

对于 10%10\% 的数据,1n1031 \leq n \leq 10^3

对于 30%30\% 的数据,1n1061 \leq n \leq 10^6

对于 50%50\% 的数据,1n1091 \leq n \leq 10^9

对于 100%100\% 的数据,1n10101 \leq n \leq 10^{10}1T101 \leq T \leq 10