Problem 1056 --G. BBP-Type Formula

1056: G. BBP-Type Formula

Time Limit: 8 Sec  Memory Limit: 256 MB
Submit: 10  Solved: 3
[Submit][Status][Web Board][Creator:]

Description

Alice 高数期末考试考了59分的好成绩,一想到即将到来的悲惨寒假,Alice决定找老师请求宽恕,仁慈的老师给了Alice一个看似与高数没什么关联的数学问题,Alice苦思了一晚上决定找Bob求助。

众所熟知的 π是一个无理数,可以通过构造无限正多边形来近似逼近数值。1995年西蒙·普劳夫提出了一个有趣的公式(BBP-TYPE),可以直接计算 π 小数点后固定位的值,不用考虑前面的位数的值。

π = Σ(k = 0 到 ∞)[1/16*(4/(8k+1) - 2/(8k+4) - 1/(8k+5) - 1/(8k+6))]


老师让Alice设计一个算法能够快速计算十六进制 π 值的第n位小数。

      比如,十六进制下 π 值等于3.243F6A8885A308D313198A2E ...,那么小数点后第一位是2,第11位是A,第15位是D

      聪明的Bob花了十分钟就解决了这个问题,然后把代码交给了你,聪明如你,加油!


Input

输入只有一个整数n(1 ≤ n ≤ 100000)

Output

输出该数据的n以及对应的值,中间以空格分开

Sample Input

1
11
111
1111
11111

Sample Output

1 2
11 A
111 D
1111 A
11111 E

HINT

Source

[Submit][Status]