問題一覧 > 通常問題

No.2393 Bit Grid Connected Component

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 140
作問者 : hiro1729 / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 9869 / 自分の提出
問題文最終更新日: 2023-07-24 17:03:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 399 (順位表) の他の問題:

Problem Statement

There is a grid with $2^{60}-1$ rows and $60$ columns, in which each row is colored black and white according to the binary representation of its row number, as follows.
The cell $(x,y)$ at row number $x$ and column number $y$ is a black cell if the $2^y$ place in the binary representation of $x$ is $1$, and a white cell if it is $0$.

Here, the connected component containing a black cell $(x, y)$ is the set of all black cells that can be reached from $(x, y)$ by moving only through black cells that are adjacent vertically or horizontally.
For each of the $T$ test cases, find the number of black cells belonging to the connected component containing the black cell $(x, y)$.


Input

The input is given from standard input in the following format.
$ T $
$ case_1 $
$ case_2 $
$ \vdots $
$ case_T $ 
Here, $ case_i $ is the $i$-th test case. Each test case is given in the following format.
$ x\ y $ 

  • $ 1 \le T \le 10^5 $
  • $ 1 \le x < 2^{60} $
  • $ 0 \le y < 60 $
  • $ (x, y) $ is a black cell. That is, the $2^y$ place in the binary representation of $x$ is $1$.

Output

Print $ T $ lines to standard output. On the $ i $-th line ($ i \leq T $), print the answer to the $ i $-th test case. Print a newline at the end.

Sample

Input
2
2 1
7 0
Output
3
7

The connected component containing $(2, 1)$ is $ (2,1),(3,0),(3,1) $, so its size is 3.
The connected component containing $(7, 0)$ is $ (7,0),(6,1),(7,1),(4,2),(5,2),(6,2),(7,2) $, so its size is 7.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。