Problem description

Jaś fascynuje się liczbami. Nic więc dziwnego, że na imieniny w prezencie otrzymał od rodziców piękną, bardzo wielką liczbę S. Rodzice nie wiedzieli jednak, że Jaś najbardziej lubi liczby szczęśliwe, to jest takie, które są podzielne przez 7.

Jaś zaraz sprawdzi, czy S jest liczbą szczęśliwą. A jeśli nie, to czy po małej zmianie może taką się stać. Przez małą zmianę Jaś rozumie zmianę dokładnie jednej cyfry o 1, czyli zwiększenie cyfry o 1 lub zmniejszenie jej o 1. Przy tym zwiększenie cyfry 9 o jeden oznacza zastąpienie jej przez 0, a zmniejszenie cyfry 0 o jeden oznacza zastąpienie jej przez 9 (inne cyfry nie ulegają zmianie przy takiej operacji).

Napisz program, obliczający na ile sposobów Jaś może dokonać malej zmiany w liczbie S, tak by stała się ona liczbą szczęśliwą.

Wejście

W pierwszym wierszu znajduje się liczba naturalna T, oznaczająca liczbę testów. W każdym z kolejnych T wierszy znajduje się jedna liczba naturalna S.

Wyjście

W i-tym wierszu należy wypisać jedną liczbę naturalną – wynik dla i-tego testu (liczbę sposobów dokonania małej zmiany, żeby liczba stała się szczęśliwa).

Ograniczenia

1 ≤ T ≤ 1000.

Każda liczba S ma nie więcej niż 10 000 cyfr dziesiętnych.

Uwaga

Jaś może zmienić najbardziej znaczącą cyfrę liczby S na zero, np. zamieniając 9 w liczbie 90 otrzyma 00, co jest zapisem liczby zero (a więc liczby szczęśliwej). Jaś nie może zaś dokładać żadnych cyfr na początku liczby (udając, że zamienia zero wiodące na jedynkę lub dziewiątkę).

Przykład

10
1
2
3
4
5
6
7
8
9
10

1
0
0
0
0
1
0
1
1
1

3
2344
1902
459751

2
0
3