Ban đầu, bạn có một đồng xu có giá trị n. Bạn có thể thực hiện phép biến đổi sau đây bất kỳ số lần nào (có thể là 0 lần):

Biến đổi một đồng xu có giá trị x (với x > 3) thành 2 đồng xu có giá trị ⌊x / 4⌋.

Hãy cho biết số lượng đồng xu tối đa mà bạn có thể có được sau khi thực hiện phép biến đổi bao nhiêu lần tùy ý.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên t (1 ≤ t ≤ 10⁴) — số lượng bộ test.
Mỗi bộ test là một dòng chứa một số nguyên n (1 ≤ n ≤ 10¹⁸).

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên — số lượng đồng xu tối đa có thể có sau khi thực hiện phép biến đổi.

Ví dụ

  Input
  4
  1
  5
  16
  1000000000000000000

  Output
  1
  2
  4
  536870912
  

Giải thích

Trong ví dụ đầu tiên, với n = 1, bạn không thể thực hiện phép biến đổi, nên kết quả là 1.

Trong ví dụ thứ hai, với n = 5, bạn có thể biến 5 thành hai đồng có giá trị 1 → tổng cộng 2 đồng.

Trong ví dụ thứ ba, với n = 16, bạn biến 16 → hai đồng 4. Mỗi đồng 4 → hai đồng 1. Tổng cộng 4 đồng.