qgg阿巴阿巴

最近，qgxx迷上了名为“qgg”的游戏

从技术上qgg的字母序列可以无线延申：

q g g q g g g q g g q g g g g q g g q g g g q g g q g g g g g ...

该序列可以用递归方式描述：

    1. S₀ 为一个长度为3的字符序列“qgg”

    2. S_k 由S_k-1，"qgg...g(2 + k个g)"，S_k-1三个序列按顺序链接组成

    Sk = S_{k - 1} + q + (k + 2)*g + S_{k - 1}

例如：

S(0) = "q g g"
S(1) = "q g g q g g g q g g"
S(2) = "q g g q g g g q g g q g g g g q g g q g g g q g g"

如你所见，此过程最终将构建一个无限长的字符串，也就是 "qgg" 游戏中使用的字符串。

请帮助qgxx确定这个无限长的字符串中的第 N 个字符是 q 还是 g。

一个整数 N。

1 ≤ N ≤ 10⁹

输出第 N个字符。

11

q
参照S(2)