Cho dãy số gồm \(N\) số nguyên dương \(A_0,A_1,\ldots,A_{N-1}\). Với mỗi \(i\) từ 0 đến \(N-1\) hãy tính:
\(\(f(i)=\sum\limits_{j|i=i, (0\leq j\leq n-1)} A_j.\)\)
Kí tự | biểu diễn phép OR.

Yêu cầu:

• Tính các giá trị \(f(i)\).

Input:

• Dòng đầu tiên gồm số nguyên dương \(T (1\leq T \leq 5)\) ứng với số test.
• Mỗi nhóm dòng trong số \(T\) dòng tiếp theo gồm:
• Dòng thứ nhất gồm một số nguyên dương \(N (N<2^18)\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_0,A_1,\ldots,A_{N-1} (1\leq A_i\leq 1000)\).

Output:

• Với mỗi test, in ra các giá trị \(f(0),f(1),\ldots ,f(N-1)\) trên một dòng.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N<2^{12}\).
• Subtask \(2\) (\(50\%\) số điểm): không giới hạn gì thêm.

1
4
1 2 3 4

1 3 4 10