Вам дано парне число \(N\) і ціле \(K\), і ви повинні знайти найбільше непарне число \(M\), менше за \(N\), щоб сума цифр у двійковому представленні \(M\) була не більше \(K\).

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(T\) (\(1 \le N \le 10^4\)) - кількість тестів.

Наступні \(T\) рядків містять цілі числа \(N,K\) (\(2 \le N \le 10^9\),\(0 \le K \le 30\)).

Формат вихідних даних

У вихідний потік вивести для кожного тесту в окремих рядках вивести шукане число або -1, якщо такого числа не існує

Примітка

Перший тест, коли N = 10, K = 2

Двійкове представлення 10 дорівнює 1010, а двійкове представлення 9 дорівнює 1001, отже, найбільше непарне число менше 10, сума цифр у його двійковому представленні не більше 2 дорівнює 9.

Приклад вхідних даних

2
10 2
6 1

Приклад вихідних даних

9
1