Little Aaryan loves going to the magic shows, One fine day after attending a magic show, he thought randomly of some numbers, He introduced some magic in them, The magic was each number had atleast one prime digit in it. He called those numbers as magical numbers. Too excited next day, he went to the magic show and asked the performer to answer his following query

Given a number N, you have to find the number of magical numbers less than or equal to N.

Input:

First line will consist of value of T i.e testcases. Next T lines will have a number N.

Output:

Output the required value as answer.

Constraints:

T <= 10^6

N <= 10^18

Sample Input:

2

100

120

Sample Output:

64

73