#include #define rf freopen("in.in", "r", stdin) #define wf freopen("out.out", "w", stdout) #define rep(i, s, n) for(int i=int(s); i<=int(n); ++i) using namespace std; const int mx = 1e5+10; int n, t, k; int a[mx]; long long calc[5111][5111]; int main() { //rf;// wf; scanf("%d", &t); while(t--) { memset(calc, 0, sizeof calc); scanf("%d %d", &n, &k); rep(i, 1, n) scanf("%d", &a[i]); rep(i, 1, n) { int cur = 0, next = 0; for(int j = i; j; --j) { next = cur | a[j]; if(cur == next) continue; rep(l, 1, min(k-1, j-1)) calc[i][l+1] = max(calc[j-1][l]+next, calc[i][l+1]); cur = next; } calc[i][1] = cur; } printf("%lld\n", calc[n][k]); } return 0; } j <= n; j++) seg_or[i][j] = seg_or[i][j - 1] | a[j]; } /* DP initialization. */ for(int i = 0; i <= n; i++) { for(int j = 0; j <= k; j++) dp[j][i] = 0; p[0][i] = 1; } for(int j = 0; j <= k; j++) p[j][n + 1] = n; /* Calculating a DP. We use, so called, Knuth optimization in it. */ for(int i = 1; i <= k; i++) { for(int j = n; j >= 1; j--) { for(int t = max(1, p[i - 1][j]); t <= p[i][j + 1]; t++) if (dp[i - 1][t - 1] + seg_or[t][j] >= dp[i][j]) { dp[i][j] = dp[i - 1][t - 1] + seg_or[t][j]; p[i][j] = t; } } } cout << dp[k][n] << endl; } return 0; }