Description

古代用九表示最大，最多。例如，九重天，疑似银河落九天等。为了找出与9关联程度最大的数，用来描述最多和最大，特地定义99天王数的概念。99天王数象征某个数与9的关联程度。 所谓99天王数，是指某个数，在其范围内含有符合条件的数值个数，这些数值或者是9的倍数，或者该数某位中含有9的数字。例如，20这个数，在其范围内，有9,18,19这三个数符合条件，所以20的99天王数是3。 今有一些数，分别找出99天王数。

Input

若干个整数N(N<20000)。

Output

对于每个数N，输出N的99天王数。

Sample

Input

10
20

Output

1
3

Source: qianneng