test 1 failed
input:
1
23
407289719 148876553 21313915 580022008 256716486 589680611 606128925 139233723 251524010 476051361 663984679 700403256 558952224 892031904 665775552 651599316 250312454 16092507 566145385 224368050 833037290 853877333 822372987
expected: 407289719 1 21313915 575475705 1 589680611 589680611 1 251524010 251524010 503048020 503048020 503048020 503048020 503048020 503048020 1 16092507 563237745 1 833037290 833037290 1
got: 536870912 134217728 16777216 536870912 268435456 536870912 536870912 134217728 268435456 536870912 536870912 536870912 536870912 536870912 536870912 536870912 268435456 16777216 536870912 268435456 536870912 536870912 536870912