Descripción

Érase una vez, Tourist se encontró en un café binario. Es un lugar muy popular e inusual.

El café ofrece a los visitantes \(K\) diferentes postres deliciosos. Los postres están numerados del \(0\) al \(k - 1\). El costo del postre número \(i\) es \(2^i\) monedas, ¡porque es un café binario! Tourist está dispuesto a gastar como máximo \(N\) monedas en degustar postres. Al mismo tiempo, no está interesado en comprar ningún postre más de una vez, porque uno es suficiente para evaluar el sabor.

¿De cuántas maneras diferentes puede comprar varios postres (posiblemente ninguno) para degustar?

Entrada

La primera línea de la entrada contiene un solo entero \(T (1 ≤ T ≤ 1000)\) (el número de casos de prueba).

Luego siguen \(T\) líneas, cada una describiendo un caso de prueba.

Cada caso de prueba se da en una sola línea y consiste en dos enteros \(N\) y \(K\) \((1 ≤ N, K ≤ 10^9)\) (el número de monedas que Tourist está dispuesto a gastar y el número de postres en el café binario).

Salida

Imprime \(T\) enteros, el \(i-ésimo\) de los cuales debe ser igual a la respuesta para el \(i-ésimo\) caso de prueba (el número de formas de comprar postres para degustar).

Ejemplo

Entrada

5
1 2
2 1
2 2
10 2
179 100

Salida

2
2
3
4
180

Nota

• Variantes para el primer ejemplo: \(\{\}\), \(\{1\}\).
• Variantes para el segundo ejemplo: \(\{\}\), \(\{1\}\).
• Variantes para el tercer ejemplo: \(\{\}\), \(\{1\}\), \(\{2\}\).
• Variantes para el cuarto ejemplo: \(\{\}\), \(\{1\}\), \(\{2\}\), \(\{1, 2\}\).