#include<cstdlib> #include<algorithm> #include<cstring> #include<cctype> #define INF 2000000000 usingnamespacestd; typedeflonglong ll; int(){ int f = 1, x = 0; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); } while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar(); return f * x; } int cnt[200005] = {0}, tot = 0; int p[10], a[200005]; voidinit(){ for(int v = 2; v <= 31622; ++v){ int pcnt = 0, t = v; for(int i = 2; i * i <= v; ++i){ if(t % i == 0){ t /= i; while(t % i == 0) t /= i; p[++pcnt] = i; if(t == 1) break ; } } if(t != 1) p[++pcnt] = t; for(int u = (v % 2 == 0) ? 1 : 2; u < v; u += 2){ int cc = u * u + v * v, flag = 1; if(cc > 1000000000) break; for(int i = 1; i <= pcnt; ++i) if(u % p[i] == 0){ flag = 0; break ; } if(!flag) continue ; int aa = v * v - u * u, bb = 2 * u * v; if(aa > bb) cnt[(aa & 131071)]++; else cnt[(bb & 131071)]++; } } } voidsolve(){ int k = read(), t; k = (1 << k), t = k - 1; for(int i = 0; i < k; ++i) a[i] = read(); ll ans = 0; for(int i = 0; i < 131072; ++i) ans += 1ll * cnt[i] * a[(i & t)]; printf("%lldn", ans); } intmain(){ int T = read(); init(); while(T--) solve(); return0; }
近期评论