SAMPLE

No            Input                                                   Output

1              1                                                           1

2              4                                                            4

3              9                                                            9

4              15                                                          2

5              29                                                          9

6              31                                                          0

7              194                                                        0

8              223                                                        1

9              220                                                        1

10            219                                                        9

11           2857                                                     9

12            2858                                                      8

13            2877                                                      5

14            28925                                                    8

15            28913                                                    5

16            2890                                                      1

17            2894                                                      1 

18            38890                                                    1

19            38934                                                    8

20            38881                                                    7

21            488877                                                  9 

22            488937                                                  7

23            5888890                                                1

24            5888903                                                1 

25            5888910                                                2

26            5888883                                                8

27            5888889                                                9   

28            68888937                                              5

29            68888889                                              7 

30            100000000                                            8