Polycarp and the Day of Pi

1000ms

262144K

Description:

On March 14, the day of the number $$$\pi$$$ is celebrated all over the world. This is a very important mathematical constant equal to the ratio of the circumference of a circle to its diameter.

Polycarp was told at school that the number $$$\pi$$$ is irrational, therefore it has an infinite number of digits in decimal notation. He wanted to prepare for the Day of the number $$$\pi$$$ by memorizing this number as accurately as possible.

Polycarp wrote out all the digits that he managed to remember. For example, if Polycarp remembered $$$\pi$$$ as $$$3.1415$$$, he wrote out 31415.

Polycarp was in a hurry and could have made a mistake, so you decided to check how many first digits of the number $$$\pi$$$ Polycarp actually remembers correctly.

Input:

The first line of the input data contains the single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases in the test.

Each test case is described by a single string of digits $$$n$$$, which was written out by Polycarp.

The string $$$n$$$ contains up to $$$30$$$ digits.

Output:

Output $$$t$$$ integers, each of which is the answer to the corresponding test case, that is how many first digits of the number $$$\pi$$$ Polycarp remembers correctly.

Sample Input:

9
000
3
4141592653
141592653589793238462643383279
31420
31415
314159265358
27182
314159265358979323846264338327

Sample Output:

Informação

Provedor Codeforces

Código CF1790A