题目描述

议会中代表们的座位安排非常重要。有些代表喜欢前排因为光线充足，有些喜欢后排因为光线较暗且更安静，还有些代表希望坐在窗边。此外，座位顺序必须绝对保密，因为相邻的代表可能会相互影响。为了避免议会中的腐败现象，决定使用超秘密代码（Hyper-secret Code）来加密座位号。长度为 $n$ 的超秘密代码记为 $SK(n)$，由所有长度为 $n$ 的二进制字符串组成，因此总共有 $2^n$ 个元素。该代码通过以下递归算法生成：

• $SK(1) = [0, 1]$
• $SK(n) = 0.SK(n-1) + 1.REV\{SK(n-1)\}$

其中：

• $[0, 1]$ 是两个长度为1的二进制字符串序列，第一个是 "0"，第二个是 "1"。
• $b.SK(x)$ 是从 $SK(x)$ 生成的代码，其中二进制数字 $b$ 被添加到 $SK(x)$ 中每个字符串的开头。
• $REV\{SK(x)\}$ 是 $SK(x)$ 的反向序列，即第一个字符串变为最后一个。
• $X + Y$ 是序列 $X$ 和 $Y$ 的拼接。

议会中的每个座位都有一个唯一的编号，编号从1开始连续递增。生成超秘密代码 $SK(n)$ 时，不断增加 $n$，直到代码的长度（即二进制字符串的数量）大于或等于最高座位号。每个座位 $s$ 被赋予序列 $SK(n)$ 中的第 $s$ 个二进制字符串。每位代表拿到自己座位的代码后，无法确定邻座是谁。

现在的问题是，当代表进入议会并拿到自己的代码后，如何快速找到对应的座位号。议会主席需要一个计算机程序，能够将任何超秘密代码转换为对应的座位号。你需要编写这个程序。

输入格式

• 第一行是一个正整数 $N$，表示测试用例的数量。
• 每个测试用例包含两行：
  • 第一行是一个整数 $k$（$1 \leq k \leq 30$），表示二进制字符串的长度。
  • 第二行是一个长度为 $k$ 的二进制字符串，由 '0' 和 '1' 组成。

输出格式

对于每个测试用例，输出一行："Poslanec P se posadi na sedadlo cislo S."（代表 #P 坐在座位 S 上），其中 $P$ 是测试用例的编号（从1开始），$S$ 是给定二进制字符串在 $SK(k)$ 中的位置。

示例输入 1

5
1
0
4
0000
4
1000
4
1111
8
10101010

示例输出 1

Poslanec 1 se posadi na sedadlo cislo 1.
Poslanec 2 se posadi na sedadlo cislo 1.
Poslanec 3 se posadi na sedadlo cislo 16.
Poslanec 4 se posadi na sedadlo cislo 11.
Poslanec 5 se posadi na sedadlo cislo 205.

来源

CTU FEE Local 1998