树与异或
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给一棵树，点有点权。多次询问，每次给出，问"点到点路径上的不同点权种类数”与“点到点路径上点权是的倍数的点个数"的异或和。即设为"点到点路径上的不同点权种类数”，为“点到点路径上点权是的倍数的点个数"，求的结果。

输入描述:

第一行，表示数据组数。
接下来每组数据第一行一个数，表示树的大小。
第二行个数，表示每个点的权值。接下来行，每行两个数表示一条边。
接下来一个数，表示询问总数。接下来行，每行三个数表示一个询问。
保证。

输出描述:

对于每组数据，第一行输出"Case #id:"，"id"表示数据序号。
接下来行，每行一个数，表示询问的答案。
示例1

输入

复制 
1
5
1 2 1 2 3
2 3
1 5
2 4
1 2
4
4 5 2
1 3 1
5 3 1
5 2 2

输出

复制 
Case #1:
1
1
7
2

说明

样例解释：对于(4,5,2)，3^2=1。对于(1,3,1)，2^3=1。对于(5,3,1)，3^4=7。对于(5,2,2)，3^1=2。