Hôm nay, algorit , WuTan , bin9638 quyết định đi mua thức ăn và nước uống vì trong tủ lạnh chẳng còn gì cả. Tuy nhiên đang trong mùa dịch Covid-19 cho nên một trong \(3\) người sẽ đi mua thức ăn và nước uống.

Để cuộc bầu cử mang tính chất công bằng, \(3\) người sẽ cùng chơi một trò chơi nhân phẩm. Mỗi người sẽ bóc thăm ngẫu nhiên một số nguyên \(x\), số nào có giá trị thăng hoa nhỏ nhất thì người đó phải đi mua thức ăn và nước uống.

Giá trị thăng hoa được định nghĩa như sau :

• Gọi \(f(x)\) là số lượng ước của \(x\) và \(u(x)\) là tổng các chữ số của \(x\).
• Giá trị thăng hoa \(= x * f(x)^2 * u(x)^3\)

Bây giờ \(3\) người chơi algorit , WuTan , bin9638 nhờ bạn tính giúp giá trị thăng hoa của cả \(3\) người. Hãy giúp \(3\) người chơi này nhé !!!

Input

• Dòng đầu tiên gồm một số nguyên dương \(T(T \le 88)\) là số lượng thử nghiệm.
• \(T\) dòng tiếp theo là \(3\) số nguyên dương \(a,b,c\) là số mà \(3\) người đã bóc được.

Output

• Có \(T\) dòng, mỗi dòng gồm 3 số nguyên là giá trị thăng hoa lần lượt của 3 người chơi.

Scoring

• Có 30% số điểm tương ứng với : \(a,b,c \le 10^5\).
• Có 30% số điểm tương ứng với : \(a,b,c \le 10^{11}\).
• Có 40% số điểm tương ứng với : \(a,b,c \le 10^{18}\).

Example

3
3 5 7
2 4 6
123123 321321 45622

324 2500 9604
64 2304 20736
217862701056 568568512512 5006740768