该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

大维最近在研究一种神秘的字符串序列，他发现这个序列具有自相似的特点，并想要快速定位其中任意位置的字符。

题目描述

现在给你一个以如下规则构建的字符串。
令 $S(0)=yoo$。对于 $i\ge1$，有

$$S(i)=S(i-1)\;+\;y\;+\;\underbrace{o\;o\;\cdots\;o}_{i\text{ 个 }}\;+\;S(i-1)\,. $$

现在会有若干次询问，询问在 $S(n)$ 上第 $k$ 个位置的字符是什么？
请注意：字符下标从 $1$ 开始计数。

输入格式

第一行一个整数 $t$，表示一共有 $t$ 组询问。
接下来 $t$ 行，每行两个整数 $n$ 和 $k$，表示询问 $S(n)$ 的第 $k$ 个字符是什么。

输出格式

输出共 $t$ 行。对于每组询问输出一个字符答案。

样例

3
2 4
2 5
2 6

y
o
y

样例解释

对于 $n=2$，有

$$S(0)=yoo,\quad S(1)=yoo\;+\;y\;+\;o\;+\;yoo=yooyoyoo, $$$$S(2)=S(1)\;+\;y\;+\;oo\;+\;S(1)\,.$$

展开后在第 $4,5,6$ 位分别是 y, o, y。

数据范围

• 对于 $40\%$ 的数据，$0\le n\le 20,\;1\le k\le 10^5$。
• 对于 $100\%$ 的数据，$1\le t\le 20,\;1\le n\le 10^9,\;1\le k\le 10^9\,$。

附件