Một cửa hàng có các món hàng, các món hàng đều có giá là ~3~ đơn vị.

Cứ ba món hàng, ta có thể gói thành gói hàng cấp ~1~. Cứ ba gói hàng cấp ~1~, ta có thể gói thành gói hàng cấp ~2~, và tương tự như vậy.

Chi phí của một gói hàng cấp ~m~, bao gồm ~3^m~ món hàng lẻ, là ~3^{m + 1} + m \times 3^{m - 1}~ đơn vị.

Có ~t~ người muốn mua hàng, mỗi người muốn mua ~n~ món hàng, với tối đa ~k~ lần mua. Hãy đưa ra chi phí nhỏ nhất để mua ~n~ món hàng, sao cho số lần mua hàng không quá ~k~ lần.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 4000~) là số người cần mua hàng.

~t~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~n~ và ~k~ (~1 \le n, k \le 10^9~).

OUTPUT

~t~ dòng, mỗi dòng là chi phí tối thiểu cho từng người. Nếu không tồn tại cách thỏa mãn, in ra ~-1~.

SAMPLE INPUT

2
3 2
10 2

SAMPLE OUTPUT

10
36

SUBTASKS