题目：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