Kim biletləri dəstə-dəstə götürərsə, o su çıxardan əldə edər…

" Brilyant əl" k/f.

Londonda lotereya təşkilatçısı özünəməxsus rekord göstərdi. 27 iyul gecəsi Olimpiada Oyunları-2012-nin açılış mərasimində lotereya uduşu keçirildi ki, bunun da nəticəsində Böyük Britaniyada yüzlərlə milyoner peyda oldu.

EuroMillions Millionaire Raffle olimpiada uduş lotereyasında milyon funtluq yüz çek oynanıldı. Bu cür kütləvi uduş və mötəbər mükafatlar təsadüfi deyildir. Onlar milli lotereyalarda iştirak etmiş Böyük Britaniya vətəndaşlarına təşəkkür idi, belə ki, lotereyadan əldə olunmuş gəlirlər idman infrastrukturunun inkişafına yönəldilmişdir. Məsələ ondadır ki, London Olimpiadasına çəkilən xərclər bir neçə milyard funtla ölçülürdü. Milli lotereya bu məqsədlə 2,2 milyard yığmaqda kömək etdi.

Olimpiadanın açılışına qədər Londona gəlmiş gənc proqramçı Vasya da olimpiada lotereyası uduşunda iştirak etmək qərarına gəldi. Bəzi ona məlum kanallarla ona nömrəsi sadə ədəd olan lotereyaların udacağı haqqında informasiya sızdı. Lotereya bileti almaq üçün növbəyə durmuş müştərinin aldığı biletə onun arxasından boylanaraq Vasyaya ona sadə bilet düşməsi üçün növbədə neçə şəxsi buraxmalı olduğunu cəld hesablamaq lazımdır. Bunun üçün onun bilməsi lazımdır ki, növbəti hansı ədəd sadə olacaq və o sizdən ona kömək etməyinizi xahiş edir. Vasyaya kömək edin.

Giriş verilənləri

Birinci sətirdə test hallarının T (0 ≤ T ≤ 1049) sayı verilir, daha sonra T sayda ayrı-ayrı sətrin hər birində növbəti baxılmış N-ci (0 ≤ N ≤ 4·109) biletin nömrəsi verilir.

Çıxış verilənləri

Hər bir test halı üçün ayrı sətirdə ehtimal olunan xoşbəxt biletin nömrəsini (aparıcı sıfırlar olmadan) verin.