#11172. A. Polycarp and the Day of PiPolycarp 和 π 之日

A. Polycarp and the Day of PiPolycarp 和 π 之日

题目:Polycarp 和 π 之日

每个测试的时间限制: 1 秒 ⏳ 内存限制: 256 兆字节 💾

在 3 月 14 日,全世界庆祝 π 之日。这是一个非常重要的数学常数,等于圆的周长与直径的比值。

Polycarp 在学校里听说 π 是无理数,因此它在十进制表示中有无穷多个数字。他想为 π 之日做准备,尽可能准确地记住这个数字。

Polycarp 写下了他记住的所有数字。例如,如果 Polycarp 记住了 π 为 3.1415,他就写下 31415。

Polycarp 很匆忙,可能会犯错,所以你决定检查 Polycarp 实际记住了多少个 π 的前几个数字。


输入

输入数据的第一行包含一个整数 t(1≤t≤103)——测试用例的数量。🌟

每个测试用例由一行描述,包含一个由 Polycarp 写下的数字字符串 n

字符串 n 最多包含 30 个数字。


输出

输出 t 个整数,每个整数是对应测试用例的答案,即 Polycarp 实际记住的 π 的前几个数字的数量。


示例

输入

9
000
3
4141592653
141592653589793238462643383279
31420
31415
314159265358
27182
314159265358979323846264338327

输出

0
1
0
0
3
5
12
0
30