Bitwise AND

Bitwise AND

Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

You are given an array A[] and the length of the array is N. Initially, all element of the array A[] is 0.
For example , if N = 5;
Initially, array looks like, A[] = {0,0,0,0,0}.
You are also given an integer K. You can perfom following operations at most K times (possibly zero),

  • In each operation select an index i from array A[], 1<=i<= N, increase it's value by 1. (Ex. A[i] = A[i] + 1).
  • After perfoming each operation K is decreased by 1.

Let see, after perfoming above operation remaining K equal to \(X\), and \(Y\) = (\(A_1\) & \(A_2\) & \(A_3\) ... & \(A_N\)).
Find the maximum possible value of \(X * Y\).

Note : '&' bitwise AND operator.

Input

First line T, the number of test cases.
In each test case, two positive integers N and K.

\(1<=T<=10^5\)
\(1<=N<=10^6\)
\(1<=K<=10^9\)

Output

In each test case, print the required answers.

Sample

Input Output
2
3 5
4 4
2
0

First test case,
N = 3, K=5;
we can perfom 3 operation on indices 1, 2, 3.
Now \(A[]\) = {1,1,1}. and \(X\) = K-3 = 5-3 = 2.
\(Y\) = (1 & 1 & 1) = 1.
\(X * Y = 2 * 1 = 2.\)
So answer is 2, which is maximum.

Information

ID
1092
Difficulty
8
Category
Implementation | Basic_Math Click to Show
Tags
# Submissions
80
Accepted
12
Accepted Ratio
15%
Uploaded By

Related

In following contests:

Brain Booster #5