Statement : Spring

Alice, Bob, and Carol visit a spring to collect water. Alice visits every $a$ days (on days $a, 2a, 3a, \ldots$), Bob every $b$ days, and Carol every $c$ days.

When only one person visits, they collect 6 liters. If two people visit the same day, each gets 3 liters; if all three visit, each gets 2 liters.

Your task is to calculate how much water Alice, Bob, and Carol each collect over $m$ days (days $1$ through $m$).

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case has one line with four integers $a$, $b$, $c$, and $m$ ($1 \le a, b, c \le 10^6$; $1 \le m \le 10^{17}$).

For each test case, print three integers — the liters collected by Alice, Bob, and Carol.

Input

4
2 1 3 10
1 1 8 5
6 20 15 1000
650650 1092 157437 100000000000000000

Output

14 38 8
15 15 0
881 236 281
845294870595 549337065358857 3774389867286

Note

In the first example ($a=2$, $b=1$, $c=3$, $m=10$): day 1 only Bob (6 L); day 2 Alice and Bob (3 each); day 3 Bob and Carol (3 each); etc. Alice totals 14, Bob 38, Carol 8.