题目描述

给定一个正整数 $n$，设 $n = p_1 \times p_2 \times \dots p_k$，其中 $p_i$ 均为质数，对 $1 \leq i < k$，$p_i \leq p_{i + 1}$。

可以证明，序列 $p_i$ 是唯一的。

对每个给定的 $n$，请你求出 $p_1, p_2, \dots p_k$。

为了避免输出过大，请你输出 $p_1, p_2, \dots p_k$ 的按位异或和。

输入格式

本题单测试点内有多组测试数据。

第一行是一个整数，表示测试数据组数 $T$。

接下来 $T$ 行，每行一个整数，表示一组数据的 $n$。

输出格式

对每组测试数据，输出一行一个整数，表示它所有质因子的按位异或和。

2
3
9

3
0

说明/提示

输入样例 #2

10
119861
788885
514352
280395
517660
855431
958212
75777
813019
67252

输出样例 #2

17124
9301
51
90
182
855431
576
80
4314
45

输入样例 #3

10
338095
484961
632
642554
80825
50799
226803
645150
414049
194197

输出样例 #3

67622
5392
77
29214
8
22
170
12
414049
194197

提示

请注意大量数据读入输出对程序效率造成的影响，选择合适的 IO 方式，避免超时。

数据规模与约定

对于全部的测试点，保证 $1 \leq T \leq 10^6$，$2 \leq n \leq 10^8$。